<!DOCTYPE html>
<html lang="zh-CN,en,zh-TW,default">
  <head hexo-theme='https://github.com/volantis-x/hexo-theme-volantis/tree/4.2.0'>
  <meta charset="utf-8">
  <!-- SEO相关 -->
  
    
  
  <!-- 渲染优化 -->
  <meta http-equiv='x-dns-prefetch-control' content='on' />
  <link rel='dns-prefetch' href='https://cdn.jsdelivr.net'>
  <link rel="preconnect" href="https://cdn.jsdelivr.net" crossorigin>
  <meta name="renderer" content="webkit">
  <meta name="force-rendering" content="webkit">
  <meta http-equiv="X-UA-Compatible" content="IE=Edge,chrome=1">
  <meta name="HandheldFriendly" content="True" >
  <meta name="apple-mobile-web-app-capable" content="yes">
  <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">

  <!-- 页面元数据 -->
  
  <title>HashMap源码解析 - Yayako&#39;s Blog</title>
  
    <meta name="keywords" content="Java,Map,源码,HashMap">
  

  
    <meta name="description" content=" ">
  

  <!-- feed -->
  

  <!-- import meta -->
  

  <!-- link -->
  
    <link rel="shortcut icon" type='image/x-icon' href="https://halo-yayako.oss-cn-hangzhou.aliyuncs.com/icons8-lamb-96_1600147384617.png">
  

  <!-- import link -->
  

  
    
<link rel="stylesheet" href="/css/first.css">

  

  
  <link rel="stylesheet" href="/css/style.css" media="print" onload="this.media='all';this.onload=null">
  <noscript><link rel="stylesheet" href="/css/style.css"></noscript>
  

  <script id="loadcss"></script>

  

<script>if (/*@cc_on!@*/false || (!!window.MSInputMethodContext && !!document.documentMode)) document.write('\x3Cscript id="_iealwn_js" data-outver="11" src="https://support.dmeng.net/ie-alert-warning/latest.js">\x3C/script>'); </script>

</head>

  <body>
    

<header id="l_header" class="l_header always shadow blur "  >
  <div class='container'>
  <div id='wrapper'>
    <div class='nav-sub'>
      <p class="title"></p>
      <ul class='switcher nav-list-h m-phone' id="pjax-header-nav-list">
        <li><a id="s-comment" class="fas fa-comments fa-fw" target="_self" href='javascript:void(0)'></a></li>
        
          <li><a id="s-toc" class="s-toc fas fa-list fa-fw" target="_self" href='javascript:void(0)'></a></li>
        
      </ul>
    </div>
		<div class="nav-main">
      
        
        <a class="title flat-box" target="_self" href='/'>
          
            <img no-lazy class='logo' src='https://yayako-blog.oss-cn-hangzhou.aliyuncs.com/settings/icons8-doughnut-100.png'/>
          
          
          
        </a>
      

			<div class='menu navigation'>
				<ul class='nav-list-h m-pc'>
          
          
          
            
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/Java/
                  
                  
                  
                    id="categoriesJava"
                  >
                  Java
                </a>
                
                  <ul class="list-v">
                    
                      
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/Java/%E5%9F%BA%E7%A1%80/
                  
                  
                  
                    id="categoriesJavaE59FBAE7A180"
                  >
                  基础
                </a>
                
              </li>
            
          
                    
                      
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/Java/JVM/
                  
                  
                  
                    id="categoriesJavaJVM"
                  >
                  JVM
                </a>
                
              </li>
            
          
                    
                      
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/Java/J.U.C/
                  
                  
                  
                    id="categoriesJavaJUC"
                  >
                  J.U.C
                </a>
                
              </li>
            
          
                    
                  </ul>
                
              </li>
            
          
          
            
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/Golang/
                  
                  
                  
                    id="categoriesGolang"
                  >
                  Golang
                </a>
                
                  <ul class="list-v">
                    
                      
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/Golang/%E5%9F%BA%E7%A1%80
                  
                  
                  
                    id="categoriesGolangE59FBAE7A180"
                  >
                  基础
                </a>
                
              </li>
            
          
                    
                  </ul>
                
              </li>
            
          
          
            
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/%E6%A1%86%E6%9E%B6/
                  
                  
                  
                    id="categoriesE6A186E69EB6"
                  >
                  框架
                </a>
                
                  <ul class="list-v">
                    
                      
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/%E6%A1%86%E6%9E%B6/SSM/
                  
                  
                  
                    id="categoriesE6A186E69EB6SSM"
                  >
                  SSM
                </a>
                
              </li>
            
          
                    
                  </ul>
                
              </li>
            
          
          
            
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/%E4%B8%AD%E9%97%B4%E4%BB%B6/
                  
                  
                  
                    id="categoriesE4B8ADE997B4E4BBB6"
                  >
                  中间件
                </a>
                
                  <ul class="list-v">
                    
                      
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/%E4%B8%AD%E9%97%B4%E4%BB%B6/Redis/
                  
                  
                  
                    id="categoriesE4B8ADE997B4E4BBB6Redis"
                  >
                  Redis
                </a>
                
              </li>
            
          
                    
                  </ul>
                
              </li>
            
          
          
            
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/MySQL/
                  
                  
                  
                    id="categoriesMySQL"
                  >
                  MySQL
                </a>
                
                  <ul class="list-v">
                    
                      
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/MySQL/%E5%9F%BA%E7%A1%80/
                  
                  
                  
                    id="categoriesMySQLE59FBAE7A180"
                  >
                  基础
                </a>
                
              </li>
            
          
                    
                      
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/MySQL/InnoDB/
                  
                  
                  
                    id="categoriesMySQLInnoDB"
                  >
                  InnoDB
                </a>
                
              </li>
            
          
                    
                  </ul>
                
              </li>
            
          
          
            
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/%E7%AE%97%E6%B3%95/
                  
                  
                  
                    id="categoriesE7AE97E6B395"
                  >
                  算法
                </a>
                
                  <ul class="list-v">
                    
                      
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/%E7%AE%97%E6%B3%95/LeetCode/
                  
                  
                  
                    id="categoriesE7AE97E6B395LeetCode"
                  >
                  LeetCode
                </a>
                
              </li>
            
          
                    
                      
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/%E7%AE%97%E6%B3%95/%E5%89%91%E6%8C%87offer/
                  
                  
                  
                    id="categoriesE7AE97E6B395E58991E68C87offer"
                  >
                  剑指offer
                </a>
                
              </li>
            
          
                    
                  </ul>
                
              </li>
            
          
          
            
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/%E5%B7%A5%E5%85%B7/
                  
                  
                  
                    id="categoriesE5B7A5E585B7"
                  >
                  工具
                </a>
                
                  <ul class="list-v">
                    
                      
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/%E5%B7%A5%E5%85%B7/Linux/
                  
                  
                  
                    id="categoriesE5B7A5E585B7Linux"
                  >
                  Linux
                </a>
                
              </li>
            
          
                    
                      
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/%E5%B7%A5%E5%85%B7/Nginx/
                  
                  
                  
                    id="categoriesE5B7A5E585B7Nginx"
                  >
                  Nginx
                </a>
                
              </li>
            
          
                    
                      
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/%E5%B7%A5%E5%85%B7/Docker/
                  
                  
                  
                    id="categoriesE5B7A5E585B7Docker"
                  >
                  Docker
                </a>
                
              </li>
            
          
                    
                  </ul>
                
              </li>
            
          
          
            
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/%E5%85%B6%E4%BB%96/
                  
                  
                  
                    id="categoriesE585B6E4BB96"
                  >
                  其他
                </a>
                
                  <ul class="list-v">
                    
                      
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/%E5%85%B6%E4%BB%96/%E9%9D%A2%E7%BB%8F/
                  
                  
                  
                    id="categoriesE585B6E4BB96E99DA2E7BB8F"
                  >
                  面经
                </a>
                
              </li>
            
          
                    
                  </ul>
                
              </li>
            
          
          
				</ul>
			</div>

      <div class="m_search">
        <form name="searchform" class="form u-search-form">
          <i class="icon fas fa-search fa-fw"></i>
          <input type="text" class="input u-search-input" placeholder="Search..." />
        </form>
      </div>

			<ul class='switcher nav-list-h m-phone'>
				
					<li><a class="s-search fas fa-search fa-fw" target="_self" href='javascript:void(0)'></a></li>
				
				<li>
          <a class="s-menu fas fa-bars fa-fw" target="_self" href='javascript:void(0)'></a>
          <ul class="menu-phone list-v navigation white-box">
            
              
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/Java/
                  
                  
                  
                    id="categoriesJava"
                  >
                  Java
                </a>
                
                  <ul class="list-v">
                    
                      
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/Java/%E5%9F%BA%E7%A1%80/
                  
                  
                  
                    id="categoriesJavaE59FBAE7A180"
                  >
                  基础
                </a>
                
              </li>
            
          
                    
                      
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/Java/JVM/
                  
                  
                  
                    id="categoriesJavaJVM"
                  >
                  JVM
                </a>
                
              </li>
            
          
                    
                      
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/Java/J.U.C/
                  
                  
                  
                    id="categoriesJavaJUC"
                  >
                  J.U.C
                </a>
                
              </li>
            
          
                    
                  </ul>
                
              </li>
            
          
            
              
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/Golang/
                  
                  
                  
                    id="categoriesGolang"
                  >
                  Golang
                </a>
                
                  <ul class="list-v">
                    
                      
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/Golang/%E5%9F%BA%E7%A1%80
                  
                  
                  
                    id="categoriesGolangE59FBAE7A180"
                  >
                  基础
                </a>
                
              </li>
            
          
                    
                  </ul>
                
              </li>
            
          
            
              
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/%E6%A1%86%E6%9E%B6/
                  
                  
                  
                    id="categoriesE6A186E69EB6"
                  >
                  框架
                </a>
                
                  <ul class="list-v">
                    
                      
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/%E6%A1%86%E6%9E%B6/SSM/
                  
                  
                  
                    id="categoriesE6A186E69EB6SSM"
                  >
                  SSM
                </a>
                
              </li>
            
          
                    
                  </ul>
                
              </li>
            
          
            
              
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/%E4%B8%AD%E9%97%B4%E4%BB%B6/
                  
                  
                  
                    id="categoriesE4B8ADE997B4E4BBB6"
                  >
                  中间件
                </a>
                
                  <ul class="list-v">
                    
                      
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/%E4%B8%AD%E9%97%B4%E4%BB%B6/Redis/
                  
                  
                  
                    id="categoriesE4B8ADE997B4E4BBB6Redis"
                  >
                  Redis
                </a>
                
              </li>
            
          
                    
                  </ul>
                
              </li>
            
          
            
              
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/MySQL/
                  
                  
                  
                    id="categoriesMySQL"
                  >
                  MySQL
                </a>
                
                  <ul class="list-v">
                    
                      
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/MySQL/%E5%9F%BA%E7%A1%80/
                  
                  
                  
                    id="categoriesMySQLE59FBAE7A180"
                  >
                  基础
                </a>
                
              </li>
            
          
                    
                      
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/MySQL/InnoDB/
                  
                  
                  
                    id="categoriesMySQLInnoDB"
                  >
                  InnoDB
                </a>
                
              </li>
            
          
                    
                  </ul>
                
              </li>
            
          
            
              
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/%E7%AE%97%E6%B3%95/
                  
                  
                  
                    id="categoriesE7AE97E6B395"
                  >
                  算法
                </a>
                
                  <ul class="list-v">
                    
                      
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/%E7%AE%97%E6%B3%95/LeetCode/
                  
                  
                  
                    id="categoriesE7AE97E6B395LeetCode"
                  >
                  LeetCode
                </a>
                
              </li>
            
          
                    
                      
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/%E7%AE%97%E6%B3%95/%E5%89%91%E6%8C%87offer/
                  
                  
                  
                    id="categoriesE7AE97E6B395E58991E68C87offer"
                  >
                  剑指offer
                </a>
                
              </li>
            
          
                    
                  </ul>
                
              </li>
            
          
            
              
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/%E5%B7%A5%E5%85%B7/
                  
                  
                  
                    id="categoriesE5B7A5E585B7"
                  >
                  工具
                </a>
                
                  <ul class="list-v">
                    
                      
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/%E5%B7%A5%E5%85%B7/Linux/
                  
                  
                  
                    id="categoriesE5B7A5E585B7Linux"
                  >
                  Linux
                </a>
                
              </li>
            
          
                    
                      
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/%E5%B7%A5%E5%85%B7/Nginx/
                  
                  
                  
                    id="categoriesE5B7A5E585B7Nginx"
                  >
                  Nginx
                </a>
                
              </li>
            
          
                    
                      
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/%E5%B7%A5%E5%85%B7/Docker/
                  
                  
                  
                    id="categoriesE5B7A5E585B7Docker"
                  >
                  Docker
                </a>
                
              </li>
            
          
                    
                  </ul>
                
              </li>
            
          
            
              
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/%E5%85%B6%E4%BB%96/
                  
                  
                  
                    id="categoriesE585B6E4BB96"
                  >
                  其他
                </a>
                
                  <ul class="list-v">
                    
                      
            
              <li>
                <a class="menuitem flat-box faa-parent animated-hover" href=/categories/%E5%85%B6%E4%BB%96/%E9%9D%A2%E7%BB%8F/
                  
                  
                  
                    id="categoriesE585B6E4BB96E99DA2E7BB8F"
                  >
                  面经
                </a>
                
              </li>
            
          
                    
                  </ul>
                
              </li>
            
          
            
          </ul>
        </li>
			</ul>
		</div>
	</div>
  </div>
</header>

    <div id="l_body">
      <div id="l_cover">
  
    
        <div id="half" class='cover-wrapper post search' style="display: ;">
          
            <div id='cover-backstretch'></div>
          
          <div class='cover-body'>
  <div class='top'>
    
    
      <p class="title">Yayako's Blog</p>
    
    
      <p class="subtitle">「Shooting for the stars when I couldn't make a killing.」</p>
    
  </div>
  <div class='bottom'>
    
      <div class="m_search">
        <form name="searchform" class="form u-search-form">
          <input type="text" class="input u-search-input" placeholder="Have a nice day!" />
          <i class="icon fas fa-search fa-fw"></i>
        </form>
      </div>
    
    <div class='menu navigation'>
      <div class='list-h'>
        
          
            <a href="/"
              
              
              id="home">
              <i class='fas fa-home fa-fw'></i><p>首页</p>
            </a>
          
            <a href="/categories/"
              
              
              id="categories">
              <i class='fas fa-folder-open fa-fw'></i><p>分类</p>
            </a>
          
            <a href="/archives/"
              
              
              id="archives">
              <i class='fas fa-archive fa-fw'></i><p>归档</p>
            </a>
          
            <a href="/tags/"
              
              
              id="tags">
              <i class='fas fa-tags fa-fw'></i><p>标签</p>
            </a>
          
            <a href="/friends/"
              
              
              id="friends">
              <i class='fas fa-link fa-fw'></i><p>友链</p>
            </a>
          
            <a href="/about/"
              
              
              id="about">
              <i class='fas fa-user fa-fw'></i><p>关于</p>
            </a>
          
        
      </div>
    </div>
  </div>
</div>

          <div id="scroll-down" style="display: none;"><i class="fa fa-chevron-down scroll-down-effects"></i></div>
        </div>
    
  
  </div>

      <div id="safearea">
        <div class="body-wrapper" id="pjax-container">
          

<div class='l_main'>
  <article class="article post white-box reveal md shadow article-type-post" id="post" itemscope itemprop="blogPost">
  


  
  <div class="article-meta" id="top">
    
    
    
      <h1 class="title">
        HashMap源码解析
      </h1>
      <div class='new-meta-box'>
        
          
            
<div class='new-meta-item author'>
  <a class='author' href="/about" rel="nofollow">
    <img no-lazy src="https://yayako-blog.oss-cn-hangzhou.aliyuncs.com/settings/icons8-cat-100%20%282%29.png">
    <p>yayako</p>
  </a>
</div>

          
        
          
            <div class="new-meta-item date">
  <a class='notlink'>
    <i class="fas fa-calendar-alt fa-fw" aria-hidden="true"></i>
    <p>发布于：2020年6月8日</p>
  </a>
</div>

          
        
          
            
  <div class="new-meta-item browse leancloud">
    <a class='notlink'>
      
      <div id="lc-pv" data-title="HashMap源码解析" data-path="/2020/06/08/HashMap/">
        <i class="fas fa-eye fa-fw" aria-hidden="true"></i>
        <span id='number'><i class="fas fa-circle-notch fa-spin fa-fw" aria-hidden="true"></i></span>
        次浏览
      </div>
    </a>
  </div>


          
        
          
            
<div class="new-meta-item comments-count">
  
  <a href="/2020/06/08/HashMap/#comments">
    <i class="fas fa-comment-dots fa-fw"></i>
    <span class="valine-comment-count" data-xid="/2020/06/08/HashMap/">0</span>
    <span class="leancloud-comments-count">&nbsp;条评论</span>
  </a>
</div>


          
        
      </div>
    
  </div>


  
  
  <h2 id="数据结构"><a href="#数据结构" class="headerlink" title="数据结构"></a>数据结构</h2><p>jdk1.7    数组 + 链表</p>
<p>jdk1.8    数组 + 链表 + 红黑树</p>
<p>当一个结点的链表长度大于8时，链表会转换成红黑树，提高查询效率,而链表长度小于6时又会退化成链表。</p>
<h3 id="为什么要引入红黑树？"><a href="#为什么要引入红黑树？" class="headerlink" title="为什么要引入红黑树？"></a>为什么要引入红黑树？</h3><p>将查找的时间复杂度从o(n)提升到o(logn)。在二叉查找树的基础上增加了着色和相关的性质使得<strong>红黑树相对平衡，从而保证了红黑树的查找、插入、删除的时间复杂度最坏为O(log n)，加快检索速率。</strong></p>
<h3 id="为什么是8？"><a href="#为什么是8？" class="headerlink" title="为什么是8？"></a>为什么是8？</h3><ol>
<li>trade-off，时间和空间的权衡。TreeNodes占用空间是普通Nodes的两倍，而链表很短时遍历速度也很快，因此需要达到一个阈值8才能够转换，当节点数变少6时，又会转回链表。</li>
<li>概率统计。源码注释里也写了，理想情况下，随机hashCode算法下所有节点的分布频率会遵循泊松分布，而链表长度达到8时的概率为0.00000006，趋近于零，因此这是根据概率统计决定的。</li>
</ol>
<h3 id="为什么是6？"><a href="#为什么是6？" class="headerlink" title="为什么是6？"></a>为什么是6？</h3><p>emmmm还不知道。</p>
<h2 id="初始化"><a href="#初始化" class="headerlink" title="初始化"></a>初始化</h2><p>我们知道，HashMap的默认初始化长度为16，而自定义长度则会取大于等于自定义长度的2的幂次数（例如输入27，最终长度为32）。</p>
<h3 id="为什么默认初始化长度为16？-为什么长度一定要是2的幂次？"><a href="#为什么默认初始化长度为16？-为什么长度一定要是2的幂次？" class="headerlink" title="为什么默认初始化长度为16？/为什么长度一定要是2的幂次？"></a>为什么默认初始化长度为16？/为什么长度一定要是2的幂次？</h3><p>为了得到低位掩码从而计算下标，为了服务于从Key映射到index的Hash算法。</p>
<p>首先要知道HashMap的下标计算方法：</p>
<h4 id="下标计算方法"><a href="#下标计算方法" class="headerlink" title="下标计算方法"></a>下标计算方法</h4><p>为了增强散列性，使元素尽可能的分散开来，从而减少碰撞去使用链表/红黑树，HashMap的发明者采用了<strong>位运算</strong>的方式来实现一个均匀分布且高效率的函数来求下标。</p>
<blockquote>
<p><strong>index = HashCode（Key） &amp; （Length - 1）</strong></p>
</blockquote>
<p>（先不讨论这个HashCode方法）</p>
<p>而只有当HashMap的长度为2的幂时，length-1 正好相当于一个<strong>低位掩码</strong>，所有二进制位都为1，才能将哈希值的高位全部归零，只保留低位值用来做数组下标访问，且保证范围在length内。</p>
<p><img src="https://img-blog.csdnimg.cn/2019102800141458.png" class="lazyload" data-srcset="https://img-blog.csdnimg.cn/2019102800141458.png" srcset="" alt="在这里插入图片描述"></p>
<p><strong>jdk1.7</strong></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">static</span> <span class="keyword">int</span> <span class="title">indexFor</span><span class="params">(<span class="keyword">int</span> h, <span class="keyword">int</span> length)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> h &amp; (length-<span class="number">1</span>);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p><strong>jdk1.8</strong></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">i = (n - <span class="number">1</span>) &amp; hash</span><br></pre></td></tr></table></figure>
<h4 id="怎么计算容量（2的幂次数）？"><a href="#怎么计算容量（2的幂次数）？" class="headerlink" title="怎么计算容量（2的幂次数）？"></a>怎么计算容量（2的幂次数）？</h4><p><strong>jdk1.7</strong></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">private</span> <span class="keyword">static</span> <span class="keyword">int</span> <span class="title">roundUpToPowerOf2</span><span class="params">(<span class="keyword">int</span> number)</span> </span>&#123;</span><br><span class="line">	<span class="comment">// assert number &gt;= 0 : &quot;number must be non-negative&quot;;</span></span><br><span class="line">	<span class="keyword">return</span> number &gt;= MAXIMUM_CAPACITY</span><br><span class="line">			? MAXIMUM_CAPACITY <span class="comment">// 超出最大容量直接返回最大容量</span></span><br><span class="line">			: (number &gt; <span class="number">1</span>) ?</span><br><span class="line">			<span class="comment">// -1后左移一位，-1应该是为了number本身就是2的幂次数的情况考虑，否则会得到更大的2的幂次数</span></span><br><span class="line">					Integer.highestOneBit((number - <span class="number">1</span>) &lt;&lt; <span class="number">1</span>)</span><br><span class="line">			: <span class="number">1</span>; <span class="comment">// 小于等于1直接返回1</span></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p><strong>Integer.highestOneBit()</strong></p>
<p>这个自己画一下就知道，通过右移和或运算返回i的二进制最高位，后面全补0，比如输入7返回8。每一次右移或运算都是为了得到一个纯1串，最后减去后面的1得到最高位为1后面补0的2的幂次数。</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">int</span> <span class="title">highestOneBit</span><span class="params">(<span class="keyword">int</span> i)</span> </span>&#123;</span><br><span class="line">    <span class="comment">// HD, Figure 3-1</span></span><br><span class="line">    i |= (i &gt;&gt;  <span class="number">1</span>);</span><br><span class="line">    i |= (i &gt;&gt;  <span class="number">2</span>);</span><br><span class="line">    i |= (i &gt;&gt;  <span class="number">4</span>);</span><br><span class="line">    i |= (i &gt;&gt;  <span class="number">8</span>);</span><br><span class="line">    i |= (i &gt;&gt; <span class="number">16</span>);</span><br><span class="line">    <span class="comment">// 到这里，i的二进制应该是形如111111</span></span><br><span class="line">    <span class="keyword">return</span> i - (i &gt;&gt;&gt; <span class="number">1</span>);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p><strong>jdk1.8</strong></p>
<p>原理相同又有点出入，1.7是<code>i - (i &gt;&gt;&gt; 1)</code>，1.8则是得到一个小于目标值的全1串再+1得到目标值。</p>
<p>举个栗子，比如输入自定义容量7 = (0111)<del>2</del>：</p>
<ul>
<li>在1.7中调用highestOneBit(12 = (1100)<del>2</del>)，通过一系列右移和或运算得到 i = (1111)<del>2</del>，减去(i&gt;&gt;&gt;1) = (0111)<del>2</del> 后得到结果 (1000)<del>2</del> = 8</li>
<li>在1.8中调用tableSizeFor(7 = (0111)<del>2</del>)，-1后通过一系列右移和或运算得到 n = (0111)<del>2</del>，+1后得到结果 (1000)<del>2</del> = 8</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * Returns a power of two size for the given target capacity.</span></span><br><span class="line"><span class="comment"> * 返回比已给目标容量大的2的幂次数，输入0返回1</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="function"><span class="keyword">static</span> <span class="keyword">final</span> <span class="keyword">int</span> <span class="title">tableSizeFor</span><span class="params">(<span class="keyword">int</span> cap)</span> </span>&#123;</span><br><span class="line">	<span class="keyword">int</span> n = cap - <span class="number">1</span>;</span><br><span class="line">	n |= n &gt;&gt;&gt; <span class="number">1</span>;</span><br><span class="line">	n |= n &gt;&gt;&gt; <span class="number">2</span>;</span><br><span class="line">	n |= n &gt;&gt;&gt; <span class="number">4</span>;</span><br><span class="line">	n |= n &gt;&gt;&gt; <span class="number">8</span>;</span><br><span class="line">	n |= n &gt;&gt;&gt; <span class="number">16</span>;</span><br><span class="line">	<span class="keyword">return</span> (n &lt; <span class="number">0</span>) ? <span class="number">1</span> : (n &gt;= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + <span class="number">1</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>


<p>前面我们知道了下标的运算方式，是通过低位掩码与哈希值相与得到哈希值的低位来做下标，这就意味着这个哈希值的计算方式几乎决定了HashMap的效率（散列值、碰撞率、分散情况），所以哈希算法的实现很关键。<strong>扰动函数</strong>就是为此而引入。<br>（jdk1.7中首次引入扰动函数，但是共做了四次扰动，1.8做了优化只用了一次）</p>
<h4 id="哈希算法-及-扰动函数"><a href="#哈希算法-及-扰动函数" class="headerlink" title="哈希算法 及 扰动函数"></a>哈希算法 及 扰动函数</h4><p>先看看源码的哈希算法实现</p>
<p><strong>jdk1.7</strong></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">final</span> <span class="keyword">int</span> <span class="title">hash</span><span class="params">(Object k)</span> </span>&#123;</span><br><span class="line">	<span class="keyword">int</span> h = hashSeed;</span><br><span class="line">	<span class="keyword">if</span> (<span class="number">0</span> != h &amp;&amp; k <span class="keyword">instanceof</span> String) &#123;</span><br><span class="line">		<span class="keyword">return</span> sun.misc.Hashing.stringHash32((String) k);</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	h ^= k.hashCode();</span><br><span class="line"></span><br><span class="line">	<span class="comment">// This function ensures that hashCodes that differ only by</span></span><br><span class="line">	<span class="comment">// constant multiples at each bit position have a bounded</span></span><br><span class="line">	<span class="comment">// number of collisions (approximately 8 at default load factor).</span></span><br><span class="line">    <span class="comment">// 这里是扰动函数</span></span><br><span class="line">	h ^= (h &gt;&gt;&gt; <span class="number">20</span>) ^ (h &gt;&gt;&gt; <span class="number">12</span>);</span><br><span class="line">	<span class="keyword">return</span> h ^ (h &gt;&gt;&gt; <span class="number">7</span>) ^ (h &gt;&gt;&gt; <span class="number">4</span>);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p><strong>jdk 1.8</strong></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">static</span> <span class="keyword">final</span> <span class="keyword">int</span> <span class="title">hash</span><span class="params">(Object key)</span> </span>&#123;</span><br><span class="line">	<span class="keyword">int</span> h;</span><br><span class="line">	<span class="keyword">return</span> (key == <span class="keyword">null</span>) ? <span class="number">0</span> : (h = key.hashCode()) ^ (h &gt;&gt;&gt; <span class="number">16</span>);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>可以看出扰动函数就是将key的哈希值h与右移16位后的h进行异或运算。</p>
<p>用一句话来概括扰动函数的作用就是：将h的hashCode右移16位并与自身相异或 相当于 使自己的高16位和低16位 相异或，得到的值<strong>既包含了自己高位的特性又包含了自己低位的特性</strong>，从而增加了之后得到的下标的不确定性，降低了碰撞的概率。</p>
<p>用一张图来演示这个扰动函数就是：<a target="_blank" rel="noopener" href="https://www.zhihu.com/question/20733617">图源</a></p>
<p><img src="https://img-blog.csdnimg.cn/20191027234121872.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjkwNzgxNw==,size_16,color_FFFFFF,t_70" class="lazyload" data-srcset="https://img-blog.csdnimg.cn/20191027234121872.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjkwNzgxNw==,size_16,color_FFFFFF,t_70" srcset="" alt="在这里插入图片描述"></p>
<p>Peter Lawley的一篇专栏文章《An introduction to optimising a hashing strategy》里的的一个实验：他随机选取了352个字符串，在他们散列值完全没有冲突的前提下，对它们做低位掩码，取数组下标。<br><img src="https://img-blog.csdnimg.cn/20191027235218810.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjkwNzgxNw==,size_16,color_FFFFFF,t_70" class="lazyload" data-srcset="https://img-blog.csdnimg.cn/20191027235218810.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjkwNzgxNw==,size_16,color_FFFFFF,t_70" srcset="" alt="在这里插入图片描述"><br>结果显示，当HashMap数组长度为512的时候，也就是用掩码取低9位的时候，在没有扰动函数的情况下，发生了103次碰撞，接近30%。而在使用了扰动函数之后只有92次碰撞。碰撞减少了将近10%。这就是扰动函数的功效。</p>
<p>jdk1.7中还有个哈希种子，还没有仔细研究，先放着<img src="https://img-blog.csdnimg.cn/2020031815292188.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjkwNzgxNw==,size_16,color_FFFFFF,t_70" class="lazyload" data-srcset="https://img-blog.csdnimg.cn/2020031815292188.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjkwNzgxNw==,size_16,color_FFFFFF,t_70" srcset="" alt="[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-5nSKykMQ-1584516366908)(/image-20200314190320318.png)]"></p>
<h2 id="put"><a href="#put" class="headerlink" title="put"></a>put</h2><p><strong>数组的第0个位置 固定放置key为null的value</strong></p>
<ol>
<li>通过扰动函数计算key的哈希值</li>
<li>如果哈希表为空，初始化</li>
<li>如果哈希表不为空，计算下标<ol>
<li>如果table[i]为空，创建新节点存入</li>
<li>如果table[i]不为空，根据HashCode和key值在链表/红黑树中寻找目标位置并更新其value值<ol>
<li>如果没有发生碰撞<ol>
<li>jdk1.7 将新节点插在当前链表头部的前面，然后再下移（<strong>头插法</strong>）</li>
<li>jdk1.8 <ol>
<li>如果是红黑树，调用红黑树的插入</li>
<li>如果是链表，遍历到链表尾部并插入新结点（<strong>尾插法</strong>），遍历的同时进行计数，当插入新节点后的计数达到阈值，就把链表转化为红黑树</li>
</ol>
</li>
</ol>
</li>
<li>如果发生碰撞，通过比较key的地址或者key的值（equals）遍历链表/红黑树获取旧值，覆盖后返回旧值</li>
<li>如果HashMap容量达到阈值<code>initialCapacity*loadFactor</code>，则进行扩容</li>
</ol>
</li>
</ol>
</li>
</ol>
<p>jdk1.8 新增链表转红黑树的阈值，因此在插入的时候必须知道链表的长度，如果长度超出这个阈值就将其转化为红黑树，因此在插入式必须遍历链表得到链表长度，于是在jdk1.8里插入结点时选择直接插在链表尾部，反正都要遍历一次，这样还保证了在扩容的时候对元素进行transfer时链表的顺序不会像1.7一样倒转，也就不会出现死循环链表。</p>
<h2 id="resize"><a href="#resize" class="headerlink" title="resize"></a>resize</h2><h3 id="扩容条件"><a href="#扩容条件" class="headerlink" title="扩容条件"></a>扩容条件</h3><p>jdk1.7     <code>(size &gt;= threshold) &amp;&amp; (null != table[bucketIndex])</code></p>
<p>存放的键值对数超出阈值，并且新增结点要插入的地方不为空</p>
<p>jdk1.8     <code>++size &gt; threshold</code></p>
<p>只要存放键值对数超出阈值就扩容</p>
<h3 id="扩容方式"><a href="#扩容方式" class="headerlink" title="扩容方式"></a>扩容方式</h3><p>默认扩容16，原数组长度，构建一个原数组长度两倍的新数组，并调用transfer将原数组的数组通过重新计算哈希值得到下标再<strong>转移</strong>到新增数组。</p>
<p>jdk1.7调用indexFor方法重新计算下标，并采用跟插入结点时一致的方式（头插法）挨个移动结点</p>
<p>jdk1.8则是根据规律将原链表拆分为两组，分别记录两个头结点，移动时直接移动头结点</p>
<p>我们会发现 <strong>HashMap扩容后，原来的元素要么在原位置，要么在原位置+原数组长度 那个位置上</strong></p>
<p>举个栗子来说：</p>
<p>原来的HashMap长度为4，table[2]上存放了A。现在要进行扩容，先创建了一个长度为8的新数组，现在要进行transfer，那么这个A要放到哪里呢？</p>
<p>我们先来根据他原本所在的位置2来倒推，我们知道<code>index = HashCode（Key） &amp; （Length - 1）</code>，那么就有<br><img src="https://img-blog.csdnimg.cn/20200318152950834.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjkwNzgxNw==,size_16,color_FFFFFF,t_70" class="lazyload" data-srcset="https://img-blog.csdnimg.cn/20200318152950834.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjkwNzgxNw==,size_16,color_FFFFFF,t_70" srcset=""></p>
<p>Hash(key) 可能为010，可能为110。</p>
<p>我们用新的长度（8 = (111)<del>2</del>）和这两个数分别再去通过Hash算法来计算新的下标会发现</p>
<ul>
<li><p>010 &amp; 111 = 010 在<strong>原位置</strong></p>
</li>
<li><p>110 &amp; 111 = 110 在原位置+4，<strong>当前下标+旧数组长度</strong></p>
</li>
</ul>
<p>在转移链表时，结点的转移和插入是一致的，jdk1.7将采用头插法（转移完后链表反转），jdk1.8在分解完链表后直接移动头结点</p>
<h3 id="为什么HashMap是线程不安全的？"><a href="#为什么HashMap是线程不安全的？" class="headerlink" title="为什么HashMap是线程不安全的？"></a>为什么HashMap是线程不安全的？</h3><p><strong>主要体现</strong></p>
<ul>
<li><p>jdk1.7中，当多线程操作同一map时，在扩容的时候会因链表反转发生循环链表或丢失数据的情况</p>
</li>
<li><p>jdk1.8中，当多线程操作同一map时，会发生数据覆盖的情况</p>
<p>在put的时候，由于put的动作不是原子性的，线程A在计算好链表位置后，挂起，线程B正常执行put操作，之后线程A恢复，会直接替换掉线程b put的值 所以依然不是线程安全的</p>
</li>
</ul>
<h3 id="为什么会遇到ConcurrentModificationException异常"><a href="#为什么会遇到ConcurrentModificationException异常" class="headerlink" title="为什么会遇到ConcurrentModificationException异常"></a>为什么会遇到ConcurrentModificationException异常</h3><p>首先我们要知道，HashMap中有个属性<code>modCount</code>，用于记录当前map的修改次数，在对map进行put、remove、clear等操作时都会增加modCount。</p>
<p>他的作用体现在对map进行遍历的时候，我们知道HashMap不是线程安全的，当对其进行遍历的时候，会先把modCount赋给迭代器内部的expectedModCount属性。当我们对map进行迭代时，他会时时刻刻比较expectedModCount和modCount是否相等，如果不相等，则说明有其他的线程对同一map进行了修改操作，于是迭代器抛出ConcurrentModificationException异常。</p>
<p>这就是<strong>Fail-Fast 机制</strong>。</p>
<blockquote>
<p>在系统设计中，快速失效系统一种可以立即报告任何可能表明故障的情况的系统。快速失效系统通常设计用于<strong>停止正常操作</strong>，而不是试图继续可能存在缺陷的过程。这种设计通常会在操作中的多个点检查系统的状态，因此可以及早检测到任何故障。快速失败模块的职责是检测错误，然后让系统的下一个最高级别处理错误。</p>
</blockquote>
<p>（你也会看到源码中有</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">int</span> expectedModCount;   <span class="comment">// For fast-fail</span></span><br></pre></td></tr></table></figure>


<h3 id="分析HashMap的containsKey方法的时间复杂度"><a href="#分析HashMap的containsKey方法的时间复杂度" class="headerlink" title="分析HashMap的containsKey方法的时间复杂度"></a>分析HashMap的containsKey方法的时间复杂度</h3><p>最好O(1)，最坏O(n)</p>
<p>因为下标是通过key的哈希值与数组长度-1得到的，因此不用便利数组，可以直接访问table[i]</p>
<p>若table[i]命中，则时间复杂度为O(1)</p>
<p>若没有直接命中，则还需遍历链表/红黑树，时间复杂度为O(n)/O(logn)</p>
<h2 id="源码解读（部分）"><a href="#源码解读（部分）" class="headerlink" title="源码解读（部分）"></a>源码解读（部分）</h2><h3 id="jdk1-7"><a href="#jdk1-7" class="headerlink" title="jdk1.7"></a>jdk1.7</h3><h4 id="构造函数"><a href="#构造函数" class="headerlink" title="构造函数"></a>构造函数</h4><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/** 参数为空的构造方法 */</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="title">HashMap</span><span class="params">()</span> </span>&#123;</span><br><span class="line">	<span class="keyword">this</span>(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/** 自定义初始化容量的构造方法 */</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="title">HashMap</span><span class="params">(<span class="keyword">int</span> initialCapacity)</span> </span>&#123;</span><br><span class="line">	<span class="keyword">this</span>(initialCapacity, DEFAULT_LOAD_FACTOR);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 构造一个空的HashMap</span></span><br><span class="line"><span class="comment"> *</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param</span>  initialCapacity 初始容量</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param</span>  loadFactor      负载因子</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@throws</span> IllegalArgumentException 初始容量/负载因子非法则抛出异常</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="title">HashMap</span><span class="params">(<span class="keyword">int</span> initialCapacity, <span class="keyword">float</span> loadFactor)</span> </span>&#123;</span><br><span class="line">	<span class="keyword">if</span> (initialCapacity &lt; <span class="number">0</span>)</span><br><span class="line">		<span class="keyword">throw</span> <span class="keyword">new</span> IllegalArgumentException(<span class="string">&quot;Illegal initial capacity: &quot;</span> +</span><br><span class="line">				initialCapacity); <span class="comment">// 初始容量为负，抛异常</span></span><br><span class="line">	<span class="keyword">if</span> (initialCapacity &gt; MAXIMUM_CAPACITY)</span><br><span class="line">		initialCapacity = MAXIMUM_CAPACITY; <span class="comment">// 初始容量超出最大容量，令初始容量为最大容量</span></span><br><span class="line">	<span class="keyword">if</span> (loadFactor &lt;= <span class="number">0</span> || Float.isNaN(loadFactor))</span><br><span class="line">		<span class="keyword">throw</span> <span class="keyword">new</span> IllegalArgumentException(<span class="string">&quot;Illegal load factor: &quot;</span> +</span><br><span class="line">				loadFactor); <span class="comment">// 初始负载因子小于等于0或NaN，抛异常</span></span><br><span class="line"></span><br><span class="line">	<span class="keyword">this</span>.loadFactor = loadFactor; <span class="comment">// 将负载因子赋值给全局变量</span></span><br><span class="line">	threshold = initialCapacity; <span class="comment">// 将初始化容量赋值给阈值</span></span><br><span class="line">	init(); </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>（os：所以其实构造函数最开始只是初始化了两个参数</p>
<p>关于<strong>负载因子</strong>：负载因子表示一个散列空间的<strong>使用程度</strong>，负载因子越大则散列表的装填程度越高，填入表中的元素越多，越容易发生冲突；负载因子越小则散列表的装填程度越低，填入表中的元素越少，越不易发生冲突，但是容易造成空间浪费。</p>
<p>关于最后的**init()**，在源码里只是个空方法，似乎是为了子类的反序列化而准备的，在hashmap构造之后、数组创建之前调用，jdk1.8以后就没有了，<a target="_blank" rel="noopener" href="https://www.zhihu.com/question/51095396">具体参考</a></p>
<h4 id="put-1"><a href="#put-1" class="headerlink" title="put"></a>put</h4><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> V <span class="title">put</span><span class="params">(K key, V value)</span> </span>&#123;</span><br><span class="line">	<span class="comment">// 如果数组为空，初始化一个数组，长度为大于阈值的最小的2的幂次数</span></span><br><span class="line">	<span class="keyword">if</span> (table == EMPTY_TABLE) &#123;</span><br><span class="line">		inflateTable(threshold);</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="comment">// 键为空，调用putForNullKey方法，因为空键固定放在0号位</span></span><br><span class="line">	<span class="keyword">if</span> (key == <span class="keyword">null</span>)</span><br><span class="line">		<span class="keyword">return</span> putForNullKey(value);</span><br><span class="line">	<span class="keyword">int</span> hash = hash(key); <span class="comment">// 计算哈希值</span></span><br><span class="line">	<span class="keyword">int</span> i = indexFor(hash, table.length); <span class="comment">// 计算下标i</span></span><br><span class="line">	<span class="comment">// 键不为空</span></span><br><span class="line">	<span class="comment">// 遍历i号位的链表</span></span><br><span class="line">	<span class="keyword">for</span> (Entry&lt;K,V&gt; e = table[i]; e != <span class="keyword">null</span>; e = e.next) &#123;</span><br><span class="line">		Object k;</span><br><span class="line">		<span class="comment">// 找到键为key的结点，判断条件：</span></span><br><span class="line">		<span class="keyword">if</span> (e.hash == hash <span class="comment">// 1.key的哈希值相同</span></span><br><span class="line">				&amp;&amp; ((k = e.key) == key || key.equals(k))) &#123; <span class="comment">// 2.key的值相同</span></span><br><span class="line">			V oldValue = e.value;</span><br><span class="line">			e.value = value; <span class="comment">// 覆写</span></span><br><span class="line">			e.recordAccess(<span class="keyword">this</span>);</span><br><span class="line">			<span class="keyword">return</span> oldValue;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="comment">// 不存在，插入</span></span><br><span class="line">	modCount++;</span><br><span class="line">	addEntry(hash, key, value, i);</span><br><span class="line">	<span class="keyword">return</span> <span class="keyword">null</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h5 id="addEntry"><a href="#addEntry" class="headerlink" title="addEntry"></a>addEntry</h5><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">addEntry</span><span class="params">(<span class="keyword">int</span> hash, K key, V value, <span class="keyword">int</span> bucketIndex)</span> </span>&#123;</span><br><span class="line">	<span class="comment">// 键值对数量超过阈值 并且 当前元素要存放的位置不为空</span></span><br><span class="line">	<span class="keyword">if</span> ((size &gt;= threshold) &amp;&amp; (<span class="keyword">null</span> != table[bucketIndex])) &#123;</span><br><span class="line">		resize(<span class="number">2</span> * table.length); <span class="comment">// 扩容</span></span><br><span class="line">		hash = (<span class="keyword">null</span> != key) ? hash(key) : <span class="number">0</span>; <span class="comment">// 重新计算哈希值</span></span><br><span class="line">		bucketIndex = indexFor(hash, table.length); <span class="comment">// 重新计算下标</span></span><br><span class="line">	&#125;</span><br><span class="line">	<span class="comment">// 加入新结点</span></span><br><span class="line">	createEntry(hash, key, value, bucketIndex);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>


<h4 id="get"><a href="#get" class="headerlink" title="get"></a>get</h4><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> V <span class="title">get</span><span class="params">(Object key)</span> </span>&#123;</span><br><span class="line">	<span class="comment">// key为空，调用getForNullKey方法，因为空键固定放在0号位</span></span><br><span class="line">	<span class="keyword">if</span> (key == <span class="keyword">null</span>)</span><br><span class="line">		<span class="keyword">return</span> getForNullKey();</span><br><span class="line">	<span class="comment">// 得到key所在的结点</span></span><br><span class="line">	Entry&lt;K,V&gt; entry = getEntry(key);</span><br><span class="line">	<span class="comment">// 结点为空直接返回null，反之获取对应val</span></span><br><span class="line">	<span class="keyword">return</span> <span class="keyword">null</span> == entry ? <span class="keyword">null</span> : entry.getValue();</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h5 id="getEntry-containsKey"><a href="#getEntry-containsKey" class="headerlink" title="getEntry / containsKey"></a>getEntry / containsKey</h5><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">containsKey</span><span class="params">(Object key)</span> </span>&#123;</span><br><span class="line">	<span class="keyword">return</span> getEntry(key) != <span class="keyword">null</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">final</span> Entry&lt;K,V&gt; <span class="title">getEntry</span><span class="params">(Object key)</span> </span>&#123;</span><br><span class="line">	<span class="comment">// 空map返回null</span></span><br><span class="line">	<span class="keyword">if</span> (size == <span class="number">0</span>) &#123;</span><br><span class="line">		<span class="keyword">return</span> <span class="keyword">null</span>;</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	<span class="keyword">int</span> hash = (key == <span class="keyword">null</span>) ? <span class="number">0</span> : hash(key); <span class="comment">// 得到key的哈希值</span></span><br><span class="line">	<span class="comment">// 计算key对应下标i，并遍历i号位的链表，找到key值对应的结点</span></span><br><span class="line">	<span class="keyword">for</span> (Entry&lt;K,V&gt; e = table[indexFor(hash, table.length)];</span><br><span class="line">	     e != <span class="keyword">null</span>;</span><br><span class="line">	     e = e.next) &#123;</span><br><span class="line">		Object k;</span><br><span class="line">        <span class="comment">// 找到键为key的结点，判断条件：</span></span><br><span class="line">		<span class="keyword">if</span> (e.hash == hash &amp;&amp; <span class="comment">// 1.key的哈希值相同</span></span><br><span class="line">				((k = e.key) == key || (key != <span class="keyword">null</span> &amp;&amp; key.equals(k)))) <span class="comment">// 2.key的值相同</span></span><br><span class="line">			<span class="keyword">return</span> e;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="comment">// 找不到就返回null</span></span><br><span class="line">	<span class="keyword">return</span> <span class="keyword">null</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>


<h4 id="resize-1"><a href="#resize-1" class="headerlink" title="resize"></a>resize</h4><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * Rehashes the contents of this map into a new array with a</span></span><br><span class="line"><span class="comment"> * larger capacity.  This method is called automatically when the</span></span><br><span class="line"><span class="comment"> * number of keys in this map reaches its threshold.</span></span><br><span class="line"><span class="comment"> * 把当前map中的元素翻新到新的更大的新map中。当前map中的键值对达到阈值就会触发扩容方法。</span></span><br><span class="line"><span class="comment"> *</span></span><br><span class="line"><span class="comment"> * If current capacity is MAXIMUM_CAPACITY, this method does not</span></span><br><span class="line"><span class="comment"> * resize the map, but sets threshold to Integer.MAX_VALUE.</span></span><br><span class="line"><span class="comment"> * This has the effect of preventing future calls.</span></span><br><span class="line"><span class="comment"> * 如果当前容量已经达到最大容量，map将不会进行扩容，而是将阈值提到Integer.MAX_VALUE，从而达到以后不会再调用扩容方法的效果</span></span><br><span class="line"><span class="comment"> *</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param</span> newCapacity the new capacity, MUST be a power of two;</span></span><br><span class="line"><span class="comment"> *        must be greater than current capacity unless current</span></span><br><span class="line"><span class="comment"> *        capacity is MAXIMUM_CAPACITY (in which case value</span></span><br><span class="line"><span class="comment"> *        is irrelevant).</span></span><br><span class="line"><span class="comment"> *        新的容量，必须是2的幂次，必须比当前容量大，除非当前容量已经达到最大容量</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">resize</span><span class="params">(<span class="keyword">int</span> newCapacity)</span> </span>&#123;</span><br><span class="line">	Entry[] oldTable = table; <span class="comment">// 当前数组</span></span><br><span class="line">	<span class="keyword">int</span> oldCapacity = oldTable.length; <span class="comment">// 当前容量</span></span><br><span class="line">	<span class="comment">// 已经达到最大容量的情况下，将阈值升到Integer.MAX_VALUE，能够有效阻止日后调用扩容</span></span><br><span class="line">	<span class="keyword">if</span> (oldCapacity == MAXIMUM_CAPACITY) &#123;</span><br><span class="line">		threshold = Integer.MAX_VALUE;</span><br><span class="line">		<span class="keyword">return</span>;</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	Entry[] newTable = <span class="keyword">new</span> Entry[newCapacity]; <span class="comment">// 创建新数组</span></span><br><span class="line">	transfer(newTable, initHashSeedAsNeeded(newCapacity)); <span class="comment">// 将旧数组中的元素全部转移到新数组</span></span><br><span class="line">	table = newTable; <span class="comment">// 新数组</span></span><br><span class="line">	threshold = (<span class="keyword">int</span>)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + <span class="number">1</span>); <span class="comment">// 重新计算阈值</span></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h5 id="transfer"><a href="#transfer" class="headerlink" title="transfer"></a>transfer</h5><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">transfer</span><span class="params">(Entry[] newTable, <span class="keyword">boolean</span> rehash)</span> </span>&#123;</span><br><span class="line">	<span class="keyword">int</span> newCapacity = newTable.length;</span><br><span class="line">	<span class="comment">// 遍历原数组的元素</span></span><br><span class="line">	<span class="keyword">for</span> (Entry&lt;K,V&gt; e : table) &#123;</span><br><span class="line">		<span class="keyword">while</span>(<span class="keyword">null</span> != e) &#123;</span><br><span class="line">			<span class="comment">// 遍历链表</span></span><br><span class="line">			Entry&lt;K,V&gt; next = e.next; <span class="comment">// 指针记录e.next</span></span><br><span class="line">			<span class="comment">// 如果需要，重新计算哈希值</span></span><br><span class="line">			<span class="keyword">if</span> (rehash) &#123;</span><br><span class="line">				e.hash = <span class="keyword">null</span> == e.key ? <span class="number">0</span> : hash(e.key);</span><br><span class="line">			&#125;</span><br><span class="line">			<span class="keyword">int</span> i = indexFor(e.hash, newCapacity); <span class="comment">// 重新计算下标</span></span><br><span class="line">			<span class="comment">// 头插法</span></span><br><span class="line">			e.next = newTable[i]; <span class="comment">// 将e插入到table[i]头部之前</span></span><br><span class="line">			newTable[i] = e; <span class="comment">// 将链表下移</span></span><br><span class="line">			e = next; <span class="comment">// 指向下一个要移动的结点</span></span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>


<h3 id="jdk1-8"><a href="#jdk1-8" class="headerlink" title="jdk1.8"></a>jdk1.8</h3><h4 id="多出的两个阈值"><a href="#多出的两个阈值" class="headerlink" title="多出的两个阈值"></a>多出的两个阈值</h4><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">static</span> <span class="keyword">final</span> <span class="keyword">int</span> TREEIFY_THRESHOLD = <span class="number">8</span>; <span class="comment">// 链表树化阈值</span></span><br><span class="line"><span class="keyword">static</span> <span class="keyword">final</span> <span class="keyword">int</span> UNTREEIFY_THRESHOLD = <span class="number">6</span>; <span class="comment">// 树链表化阈值</span></span><br></pre></td></tr></table></figure>
<h4 id="结点的引入"><a href="#结点的引入" class="headerlink" title="结点的引入"></a>结点的引入</h4><p> <code>Node&lt;K,V&gt;</code></p>
<h4 id="构造函数-1"><a href="#构造函数-1" class="headerlink" title="构造函数"></a>构造函数</h4><p>和1.7几乎相同，不做注释，两点不同的是</p>
<ul>
<li>移除了钩子函数init()</li>
<li>1.7是直接将自定义容量赋给threshold，在inflateTable时才计算数组长度，而1.8是直接计算数组长度赋给threshold</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * Constructs an empty &lt;tt&gt;HashMap&lt;/tt&gt; with the specified initial</span></span><br><span class="line"><span class="comment"> * capacity and load factor.</span></span><br><span class="line"><span class="comment"> *</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param</span>  initialCapacity the initial capacity</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param</span>  loadFactor      the load factor</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@throws</span> IllegalArgumentException if the initial capacity is negative</span></span><br><span class="line"><span class="comment"> *         or the load factor is nonpositive</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="title">HashMap</span><span class="params">(<span class="keyword">int</span> initialCapacity, <span class="keyword">float</span> loadFactor)</span> </span>&#123;</span><br><span class="line">	<span class="keyword">if</span> (initialCapacity &lt; <span class="number">0</span>)</span><br><span class="line">		<span class="keyword">throw</span> <span class="keyword">new</span> IllegalArgumentException(<span class="string">&quot;Illegal initial capacity: &quot;</span> +</span><br><span class="line">				initialCapacity);</span><br><span class="line">	<span class="keyword">if</span> (initialCapacity &gt; MAXIMUM_CAPACITY)</span><br><span class="line">		initialCapacity = MAXIMUM_CAPACITY;</span><br><span class="line">	<span class="keyword">if</span> (loadFactor &lt;= <span class="number">0</span> || Float.isNaN(loadFactor))</span><br><span class="line">		<span class="keyword">throw</span> <span class="keyword">new</span> IllegalArgumentException(<span class="string">&quot;Illegal load factor: &quot;</span> +</span><br><span class="line">				loadFactor);</span><br><span class="line">	<span class="keyword">this</span>.loadFactor = loadFactor;</span><br><span class="line">	<span class="keyword">this</span>.threshold = tableSizeFor(initialCapacity);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>


<h4 id="put-2"><a href="#put-2" class="headerlink" title="put"></a>put</h4><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * Associates the specified value with the specified key in this map.</span></span><br><span class="line"><span class="comment"> * If the map previously contained a mapping for the key, the old</span></span><br><span class="line"><span class="comment"> * value is replaced.</span></span><br><span class="line"><span class="comment"> * 以给定的键值对寻找是否有相同的键值，如果有，覆写。</span></span><br><span class="line"><span class="comment"> *</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param</span> key key with which the specified value is to be associated 键</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param</span> value value to be associated with the specified key 值</span></span><br><span class="line"><span class="comment"> *</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return</span> the previous value associated with &lt;tt&gt;key&lt;/tt&gt;, or</span></span><br><span class="line"><span class="comment"> *         &lt;tt&gt;null&lt;/tt&gt; if there was no mapping for &lt;tt&gt;key&lt;/tt&gt;.</span></span><br><span class="line"><span class="comment"> *         (A &lt;tt&gt;null&lt;/tt&gt; return can also indicate that the map</span></span><br><span class="line"><span class="comment"> *         previously associated &lt;tt&gt;null&lt;/tt&gt; with &lt;tt&gt;key&lt;/tt&gt;.)</span></span><br><span class="line"><span class="comment"> *         有相同的key，则返回旧值；没有就返回null</span></span><br><span class="line"><span class="comment"> *         返回值同时可以作map中是否包含该key值的判断</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> V <span class="title">put</span><span class="params">(K key, V value)</span> </span>&#123;</span><br><span class="line">	<span class="comment">// 计算哈希值开始找</span></span><br><span class="line">	<span class="comment">// onlyIfAbsent: false &lt;=&gt; 允许覆写</span></span><br><span class="line">	<span class="comment">// evict: true &lt;=&gt; 插入结点后是否允许操作（看了下应该是给子类LinkedHashMap用的</span></span><br><span class="line">	<span class="keyword">return</span> putVal(hash(key), key, value, <span class="keyword">false</span>, <span class="keyword">true</span>);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h5 id="putVal"><a href="#putVal" class="headerlink" title="putVal"></a>putVal</h5><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">final</span> V <span class="title">putVal</span><span class="params">(<span class="keyword">int</span> hash, K key, V value, <span class="keyword">boolean</span> onlyIfAbsent,</span></span></span><br><span class="line"><span class="function"><span class="params">               <span class="keyword">boolean</span> evict)</span> </span>&#123;</span><br><span class="line">	Node&lt;K,V&gt;[] tab; Node&lt;K,V&gt; p; <span class="keyword">int</span> n, i;</span><br><span class="line">	<span class="comment">// 数组为空 或 数组长度为0，构造table数组</span></span><br><span class="line">	<span class="keyword">if</span> ((tab = table) == <span class="keyword">null</span> || (n = tab.length) == <span class="number">0</span>)</span><br><span class="line">		n = (tab = resize()).length;</span><br><span class="line">	<span class="comment">// 计算下标i，数组i号位的结点p为空，直接插入新结点</span></span><br><span class="line">	<span class="keyword">if</span> ((p = tab[i = (n - <span class="number">1</span>) &amp; hash]) == <span class="keyword">null</span>)</span><br><span class="line">		tab[i] = newNode(hash, key, value, <span class="keyword">null</span>);</span><br><span class="line">	<span class="keyword">else</span> &#123;</span><br><span class="line">		<span class="comment">// i号位不为空，遍历</span></span><br><span class="line">		Node&lt;K,V&gt; e; K k;</span><br><span class="line">		<span class="comment">// 头结点是要找的结点（key的哈希值或key的值相同），e指向p</span></span><br><span class="line">		<span class="keyword">if</span> (p.hash == hash &amp;&amp; <span class="comment">// key的哈希值相同</span></span><br><span class="line">				((k = p.key) == key || (key != <span class="keyword">null</span> &amp;&amp; key.equals(k)))) <span class="comment">// 或 key值相同</span></span><br><span class="line">			e = p;</span><br><span class="line">		<span class="comment">// p是树节点，调用红黑树的插入方法</span></span><br><span class="line">		<span class="keyword">else</span> <span class="keyword">if</span> (p <span class="keyword">instanceof</span> TreeNode)</span><br><span class="line">			e = ((TreeNode&lt;K,V&gt;)p).putTreeVal(<span class="keyword">this</span>, tab, hash, key, value);</span><br><span class="line">		<span class="comment">// p是链表结点</span></span><br><span class="line">		<span class="keyword">else</span> &#123;</span><br><span class="line">			<span class="comment">// 遍历链表，同时计数binCount，用于判断是否该树化链表</span></span><br><span class="line">			<span class="keyword">for</span> (<span class="keyword">int</span> binCount = <span class="number">0</span>; ; ++binCount) &#123;</span><br><span class="line">				<span class="comment">// 遍历到尾结点</span></span><br><span class="line">				<span class="keyword">if</span> ((e = p.next) == <span class="keyword">null</span>) &#123;</span><br><span class="line">					<span class="comment">// 插入结点</span></span><br><span class="line">					p.next = newNode(hash, key, value, <span class="keyword">null</span>);</span><br><span class="line">					<span class="comment">// 判断是否超出阈值，是则树化</span></span><br><span class="line">                    <span class="comment">// -1是因为除去了数组内的头结点</span></span><br><span class="line">					<span class="keyword">if</span> (binCount &gt;= TREEIFY_THRESHOLD - <span class="number">1</span>) <span class="comment">// -1 for 1st</span></span><br><span class="line">						treeifyBin(tab, hash);</span><br><span class="line">					<span class="keyword">break</span>;</span><br><span class="line">				&#125;</span><br><span class="line">				<span class="comment">// 找到目标结点，赋值给e</span></span><br><span class="line">				<span class="keyword">if</span> (e.hash == hash &amp;&amp;</span><br><span class="line">						((k = e.key) == key || (key != <span class="keyword">null</span> &amp;&amp; key.equals(k))))</span><br><span class="line">					<span class="keyword">break</span>;</span><br><span class="line">				p = e;</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="comment">// 找到目标结点，覆写（如果允许的话 或 旧值为null）并返回旧值</span></span><br><span class="line">		<span class="keyword">if</span> (e != <span class="keyword">null</span>) &#123; <span class="comment">// existing mapping for key</span></span><br><span class="line">			V oldValue = e.value;</span><br><span class="line">			<span class="keyword">if</span> (!onlyIfAbsent || oldValue == <span class="keyword">null</span>)</span><br><span class="line">				e.value = value;</span><br><span class="line">			afterNodeAccess(e);</span><br><span class="line">			<span class="keyword">return</span> oldValue;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	++modCount; <span class="comment">// 操作次数++</span></span><br><span class="line">	<span class="comment">// 键值对数量增加并判断是否该扩容（与1.7相比判断条件少了</span></span><br><span class="line">	<span class="keyword">if</span> (++size &gt; threshold)</span><br><span class="line">		resize();</span><br><span class="line">	afterNodeInsertion(evict);</span><br><span class="line">	<span class="keyword">return</span> <span class="keyword">null</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>注意两点</p>
<ul>
<li>先插入结点，再判断是否需要树化</li>
<li>关于树化的阈值判断，模拟一下会知道，其实是当链表长度<strong>超出</strong>8才会转红黑树。<br><img src="https://img-blog.csdnimg.cn/20200318153233119.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjkwNzgxNw==,size_16,color_FFFFFF,t_70" class="lazyload" data-srcset="https://img-blog.csdnimg.cn/20200318153233119.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjkwNzgxNw==,size_16,color_FFFFFF,t_70" srcset="" alt="在这里插入图片描述"></li>
</ul>
<h4 id="get-1"><a href="#get-1" class="headerlink" title="get"></a>get</h4><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> V <span class="title">get</span><span class="params">(Object key)</span> </span>&#123;</span><br><span class="line">	Node&lt;K,V&gt; e;</span><br><span class="line">    <span class="comment">// 计算哈希值寻找结点，有就返回val，没有就返回null</span></span><br><span class="line">	<span class="keyword">return</span> (e = getNode(hash(key), key)) == <span class="keyword">null</span> ? <span class="keyword">null</span> : e.value;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h5 id="getNode-containsKey"><a href="#getNode-containsKey" class="headerlink" title="getNode / containsKey"></a>getNode / containsKey</h5><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">containsKey</span><span class="params">(Object key)</span> </span>&#123;</span><br><span class="line">   <span class="keyword">return</span> getNode(hash(key), key) != <span class="keyword">null</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>os：1.8真的很喜欢把赋值语句放在条件判断里…….</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">final</span> Node&lt;K,V&gt; <span class="title">getNode</span><span class="params">(<span class="keyword">int</span> hash, Object key)</span> </span>&#123;</span><br><span class="line">	Node&lt;K,V&gt;[] tab; <span class="comment">// 数组</span></span><br><span class="line">	Node&lt;K,V&gt; first, e; <span class="comment">// 结点</span></span><br><span class="line">	<span class="keyword">int</span> n;</span><br><span class="line">	K k;</span><br><span class="line">	<span class="keyword">if</span> ((tab = table) != <span class="keyword">null</span> <span class="comment">// 数组不为空</span></span><br><span class="line">			&amp;&amp; (n = tab.length) &gt; <span class="number">0</span> <span class="comment">// 数组长度大于0</span></span><br><span class="line">			&amp;&amp; (first = tab[(n - <span class="number">1</span>) &amp; hash]) != <span class="keyword">null</span>) &#123; <span class="comment">// 计算下标i，i号位不为空</span></span><br><span class="line">		<span class="keyword">if</span> (first.hash == hash &amp;&amp; <span class="comment">// always check first node 首先检查头结点是否是目标结点，是就返回</span></span><br><span class="line">				((k = first.key) == key || (key != <span class="keyword">null</span> &amp;&amp; key.equals(k))))</span><br><span class="line">			<span class="keyword">return</span> first;</span><br><span class="line">		<span class="keyword">if</span> ((e = first.next) != <span class="keyword">null</span>) &#123;</span><br><span class="line">			<span class="comment">// 如果头结点后连得第一个是树节点，调用树的get方法</span></span><br><span class="line">			<span class="keyword">if</span> (first <span class="keyword">instanceof</span> TreeNode)</span><br><span class="line">				<span class="keyword">return</span> ((TreeNode&lt;K,V&gt;)first).getTreeNode(hash, key);</span><br><span class="line">			<span class="comment">// 如果不是，那就是链表结构，那就遍历寻找</span></span><br><span class="line">			<span class="keyword">do</span> &#123;</span><br><span class="line">				<span class="comment">// 找到了就返回</span></span><br><span class="line">				<span class="keyword">if</span> (e.hash == hash &amp;&amp;</span><br><span class="line">						((k = e.key) == key || (key != <span class="keyword">null</span> &amp;&amp; key.equals(k))))</span><br><span class="line">					<span class="keyword">return</span> e;</span><br><span class="line">			&#125; <span class="keyword">while</span> ((e = e.next) != <span class="keyword">null</span>);</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="comment">// 找不到就返回null</span></span><br><span class="line">	<span class="keyword">return</span> <span class="keyword">null</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>


<h4 id="resize-2"><a href="#resize-2" class="headerlink" title="resize"></a>resize</h4><p>建议先把前面的扩容方式计算新下标的思路看一下</p>
<p>大概意思就是根据高位是0还是1来确定最后存的下标位置，0就保持原位，1就向后移一个旧长度的位置，这个结果和重新计算下标的结果是一致的<br><img src="https://img-blog.csdnimg.cn/20200318153257722.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjkwNzgxNw==,size_16,color_FFFFFF,t_70" class="lazyload" data-srcset="https://img-blog.csdnimg.cn/20200318153257722.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjkwNzgxNw==,size_16,color_FFFFFF,t_70" srcset="" alt="在这里插入图片描述"></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * Initializes or doubles table size.  If null, allocates in</span></span><br><span class="line"><span class="comment"> * accord with initial capacity target held in field threshold.</span></span><br><span class="line"><span class="comment"> * Otherwise, because we are using power-of-two expansion, the</span></span><br><span class="line"><span class="comment"> * elements from each bin must either stay at same index, or move</span></span><br><span class="line"><span class="comment"> * with a power of two offset in the new table.</span></span><br><span class="line"><span class="comment"> * 初始化或翻倍数组。如果为空，初始化数组。</span></span><br><span class="line"><span class="comment"> *</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return</span> the table</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">final</span> Node&lt;K,V&gt;[] resize() &#123;</span><br><span class="line">	Node&lt;K,V&gt;[] oldTab = table; <span class="comment">// 暂存旧table数组</span></span><br><span class="line">	<span class="keyword">int</span> oldCap = (oldTab == <span class="keyword">null</span>) ? <span class="number">0</span> : oldTab.length; <span class="comment">// 暂存旧容量，如果是初始化调用扩容方法，旧容量为空，赋0</span></span><br><span class="line">	<span class="keyword">int</span> oldThr = threshold; <span class="comment">// 暂存旧阈值</span></span><br><span class="line">	<span class="keyword">int</span> newCap, newThr = <span class="number">0</span>;</span><br><span class="line">	<span class="comment">// 旧容量不为0</span></span><br><span class="line">	<span class="keyword">if</span> (oldCap &gt; <span class="number">0</span>) &#123;</span><br><span class="line">		<span class="comment">// 旧容量达到最大容量，不再扩容，将阈值提高至Integer.MAX_VALUE，有效阻止以后再度出现达到阈值的情况</span></span><br><span class="line">		<span class="keyword">if</span> (oldCap &gt;= MAXIMUM_CAPACITY) &#123;</span><br><span class="line">			threshold = Integer.MAX_VALUE;</span><br><span class="line">			<span class="keyword">return</span> oldTab;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="comment">// 左移翻倍容量和阈值（前提是不超过最大容量并且旧容量需要超出默认容量</span></span><br><span class="line">		<span class="keyword">else</span> <span class="keyword">if</span> ((newCap = oldCap &lt;&lt; <span class="number">1</span>) &lt; MAXIMUM_CAPACITY &amp;&amp;</span><br><span class="line">				oldCap &gt;= DEFAULT_INITIAL_CAPACITY)</span><br><span class="line">			newThr = oldThr &lt;&lt; <span class="number">1</span>; <span class="comment">// double threshold</span></span><br><span class="line">	&#125;</span><br><span class="line">	<span class="comment">// 旧容量为0，即table数组还未创建</span></span><br><span class="line">	<span class="comment">// 为带参构造方法使用HashMap(int initialCapacity)及HashMap(int initialCapacity, float loadFactor)</span></span><br><span class="line">	<span class="comment">// 因为初始化容量一开始是被存放在threshold中的</span></span><br><span class="line">	<span class="keyword">else</span> <span class="keyword">if</span> (oldThr &gt; <span class="number">0</span>) <span class="comment">// initial capacity was placed in threshold</span></span><br><span class="line">		newCap = oldThr;</span><br><span class="line">	<span class="comment">// 旧容量为0，即table数组还未创建</span></span><br><span class="line">	<span class="comment">// 为无参构造方法使用HashMap()，使用默认值</span></span><br><span class="line">	<span class="keyword">else</span> &#123;               <span class="comment">// zero initial threshold signifies using defaults</span></span><br><span class="line">		newCap = DEFAULT_INITIAL_CAPACITY;</span><br><span class="line">		newThr = (<span class="keyword">int</span>)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); <span class="comment">// 初始化阈值</span></span><br><span class="line">	&#125;</span><br><span class="line">    <span class="comment">// 如果新阈值为0</span></span><br><span class="line">    <span class="comment">// 一种情况是使用了带参构造方法（else if (oldThr &gt; 0)）</span></span><br><span class="line">    <span class="comment">// 另一种是旧容量未达到默认容量大小或翻倍后超出最大容量（else if ((newCap = oldCap &lt;&lt; 1) &lt; MAXIMUM_CAPACITY &amp;&amp;</span></span><br><span class="line">    <span class="comment">//						oldCap &gt;= DEFAULT_INITIAL_CAPACITY)）</span></span><br><span class="line">    <span class="keyword">if</span> (newThr == <span class="number">0</span>) &#123;</span><br><span class="line">		<span class="keyword">float</span> ft = (<span class="keyword">float</span>)newCap * loadFactor; <span class="comment">// 计算新阈值</span></span><br><span class="line">		newThr = (newCap &lt; MAXIMUM_CAPACITY &amp;&amp; ft &lt; (<span class="keyword">float</span>)MAXIMUM_CAPACITY ?</span><br><span class="line">				(<span class="keyword">int</span>)ft : Integer.MAX_VALUE); <span class="comment">// 新容量满足要求</span></span><br><span class="line">	&#125;</span><br><span class="line">	<span class="comment">// 赋阈值</span></span><br><span class="line">	threshold = newThr;</span><br><span class="line">	<span class="meta">@SuppressWarnings(&#123;&quot;rawtypes&quot;,&quot;unchecked&quot;&#125;)</span></span><br><span class="line">			<span class="comment">// 创建新数组</span></span><br><span class="line">	Node&lt;K,V&gt;[] newTab = (Node&lt;K,V&gt;[])<span class="keyword">new</span> Node[newCap];</span><br><span class="line">	table = newTab; <span class="comment">// 赋给全局变量</span></span><br><span class="line">	<span class="comment">// 这里开始实施转移，transfer</span></span><br><span class="line">	<span class="keyword">if</span> (oldTab != <span class="keyword">null</span>) &#123;</span><br><span class="line">		<span class="comment">// 第一层，数组结点遍历</span></span><br><span class="line">		<span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j &lt; oldCap; ++j) &#123;</span><br><span class="line">			Node&lt;K,V&gt; e;</span><br><span class="line">			<span class="comment">// 数组结点</span></span><br><span class="line">			<span class="keyword">if</span> ((e = oldTab[j]) != <span class="keyword">null</span>) &#123;</span><br><span class="line">				oldTab[j] = <span class="keyword">null</span>; <span class="comment">// 释放旧数组</span></span><br><span class="line">				<span class="keyword">if</span> (e.next == <span class="keyword">null</span>) <span class="comment">// 尾结点，直接转移</span></span><br><span class="line">					newTab[e.hash &amp; (newCap - <span class="number">1</span>)] = e;</span><br><span class="line">				<span class="keyword">else</span> <span class="keyword">if</span> (e <span class="keyword">instanceof</span> TreeNode) <span class="comment">// 树节点，调用树的split方法</span></span><br><span class="line">					((TreeNode&lt;K,V&gt;)e).split(<span class="keyword">this</span>, newTab, j, oldCap);</span><br><span class="line">				<span class="comment">// 链表结点，保留之前的顺序（尾插法</span></span><br><span class="line">				<span class="keyword">else</span> &#123; <span class="comment">// preserve order</span></span><br><span class="line">					<span class="comment">// 第二层，链表遍历</span></span><br><span class="line">					<span class="comment">// （我们以该链表原本位置在010（2），旧容量为100（4）举例子，分析已知原本的哈希值可能为010，可能为110</span></span><br><span class="line"></span><br><span class="line">					<span class="comment">// head记录头结点，tail记录尾结点</span></span><br><span class="line">					Node&lt;K,V&gt; loHead = <span class="keyword">null</span>, loTail = <span class="keyword">null</span>; <span class="comment">// lo表示low表示0，记录要转移的结点</span></span><br><span class="line">					Node&lt;K,V&gt; hiHead = <span class="keyword">null</span>, hiTail = <span class="keyword">null</span>; <span class="comment">// hi表示high表示1，记录保留在原位置的结点</span></span><br><span class="line">					Node&lt;K,V&gt; next;</span><br><span class="line">					<span class="keyword">do</span> &#123;</span><br><span class="line">						next = e.next;</span><br><span class="line">						<span class="keyword">if</span> ((e.hash &amp; oldCap) == <span class="number">0</span>) &#123; <span class="comment">// 高位为0（010</span></span><br><span class="line">							<span class="keyword">if</span> (loTail == <span class="keyword">null</span>)</span><br><span class="line">								loHead = e;</span><br><span class="line">							<span class="keyword">else</span></span><br><span class="line">								loTail.next = e;</span><br><span class="line">							loTail = e;</span><br><span class="line">						&#125;</span><br><span class="line">						<span class="keyword">else</span> &#123; <span class="comment">// 高位为1（110</span></span><br><span class="line">							<span class="keyword">if</span> (hiTail == <span class="keyword">null</span>)</span><br><span class="line">								hiHead = e;</span><br><span class="line">							<span class="keyword">else</span></span><br><span class="line">								hiTail.next = e;</span><br><span class="line">							hiTail = e;</span><br><span class="line">						&#125;</span><br><span class="line">					&#125; <span class="keyword">while</span> ((e = next) != <span class="keyword">null</span>);</span><br><span class="line">					<span class="comment">// 高位为0的链表，保持原位置</span></span><br><span class="line">					<span class="keyword">if</span> (loTail != <span class="keyword">null</span>) &#123;</span><br><span class="line">						loTail.next = <span class="keyword">null</span>;</span><br><span class="line">						newTab[j] = loHead;</span><br><span class="line">					&#125;</span><br><span class="line">					<span class="comment">// 高位为1的链表，转移阵地</span></span><br><span class="line">					<span class="keyword">if</span> (hiTail != <span class="keyword">null</span>) &#123;</span><br><span class="line">						hiTail.next = <span class="keyword">null</span>;</span><br><span class="line">						newTab[j + oldCap] = hiHead;</span><br><span class="line">					&#125;</span><br><span class="line">				&#125;</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="comment">// 返回新数组</span></span><br><span class="line">	<span class="keyword">return</span> newTab;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>




<h2 id="jdk1-7到1-8的主要变化"><a href="#jdk1-7到1-8的主要变化" class="headerlink" title="jdk1.7到1.8的主要变化"></a>jdk1.7到1.8的主要变化</h2><ol>
<li><h3 id="数据结构改变"><a href="#数据结构改变" class="headerlink" title="数据结构改变"></a>数据结构改变</h3><ol>
<li>jdk1.7，数组+链表</li>
<li>jdk1.8，数组+链表+红黑树</li>
</ol>
</li>
<li><h3 id="链表节点插入"><a href="#链表节点插入" class="headerlink" title="链表节点插入"></a>链表节点插入</h3><ol>
<li>jdk1.7，头插法，再下移</li>
<li>jdk1.8，尾插法</li>
</ol>
</li>
<li><h3 id="扩容"><a href="#扩容" class="headerlink" title="扩容"></a>扩容</h3><ol>
<li><h4 id="扩容条件减少"><a href="#扩容条件减少" class="headerlink" title="扩容条件减少"></a>扩容条件减少</h4><ol>
<li>jdk1.7，达到阈值并且新增结点发生碰撞才扩容，也就是说，如果达到阈值后，新增节点插入位置为空，则先不扩容</li>
<li>jdk1.8，只要达到阈值就扩容</li>
</ol>
</li>
<li><h4 id="扩容方式（针对链表而言）"><a href="#扩容方式（针对链表而言）" class="headerlink" title="扩容方式（针对链表而言）"></a>扩容方式（针对链表而言）</h4><ol>
<li>jdk1.7，采取和插入时一致的方式，头插法，再下移</li>
<li>jdk1.8，拆分链表后直接移动头结点</li>
</ol>
</li>
<li><h4 id="扩容下标计算"><a href="#扩容下标计算" class="headerlink" title="扩容下标计算"></a>扩容下标计算</h4><ol>
<li>jdk1.7，重新计算</li>
<li>jdk1.8，根据高位二进制决定，为0则下标不变，为1则往后移动一个旧数组长度的距离</li>
</ol>
</li>
</ol>
</li>
<li><h3 id="简化了哈希算法"><a href="#简化了哈希算法" class="headerlink" title="简化了哈希算法"></a>简化了哈希算法</h3><ol>
<li>jdk1.7，使用了哈希种子，使用了四次扰动函数</li>
<li>jdk1.8，使用一次扰动函数</li>
</ol>
</li>
</ol>

  
  
    
    <div class='footer'>
      
      
      
        <div class='copyright'>
          <blockquote>
            
              
                <p>博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议</p>

              
            
              
                <p>本文永久链接是：<a href=https://www.yayako.cn/2020/06/08/HashMap/>https://www.yayako.cn/2020/06/08/HashMap/</a></p>
              
            
          </blockquote>
        </div>
      
      
    </div>
  
  
    


  <div class='article-meta' id="bottom">
    <div class='new-meta-box'>
      
        
          <div class="new-meta-item date" itemprop="dateUpdated" datetime="2021-01-22T16:19:06+08:00">
  <a class='notlink'>
    <i class="fas fa-edit fa-fw" aria-hidden="true"></i>
    <p>更新于：2021年1月22日</p>
  </a>
</div>

        
      
        
          
  
  <div class="new-meta-item meta-tags"><a class="tag" href="/tags/Java/" rel="nofollow"><i class="fas fa-hashtag fa-fw" aria-hidden="true"></i><p>Java</p></a></div> <div class="new-meta-item meta-tags"><a class="tag" href="/tags/Map/" rel="nofollow"><i class="fas fa-hashtag fa-fw" aria-hidden="true"></i><p>Map</p></a></div> <div class="new-meta-item meta-tags"><a class="tag" href="/tags/%E6%BA%90%E7%A0%81/" rel="nofollow"><i class="fas fa-hashtag fa-fw" aria-hidden="true"></i><p>源码</p></a></div> <div class="new-meta-item meta-tags"><a class="tag" href="/tags/HashMap/" rel="nofollow"><i class="fas fa-hashtag fa-fw" aria-hidden="true"></i><p>HashMap</p></a></div>


        
      
        
          
  <div class="new-meta-item share -mob-share-list">
  <div class="-mob-share-list share-body">
    
      
        <a class="-mob-share-qq" title="" rel="external nofollow noopener noreferrer noopener"
          
          target="_blank" href="http://connect.qq.com/widget/shareqq/index.html?url=https://www.yayako.cn/2020/06/08/HashMap/&title=HashMap源码解析 - Yayako's Blog&summary= "
          
          >
          
            <img src="https://cdn.jsdelivr.net/gh/volantis-x/cdn-org/logo/128/qq.png" class="lazyload" data-srcset="https://cdn.jsdelivr.net/gh/volantis-x/cdn-org/logo/128/qq.png" srcset="">
          
        </a>
      
    
      
        <a class="-mob-share-qzone" title="" rel="external nofollow noopener noreferrer noopener"
          
          target="_blank" href="https://sns.qzone.qq.com/cgi-bin/qzshare/cgi_qzshare_onekey?url=https://www.yayako.cn/2020/06/08/HashMap/&title=HashMap源码解析 - Yayako's Blog&summary= "
          
          >
          
            <img src="https://cdn.jsdelivr.net/gh/volantis-x/cdn-org/logo/128/qzone.png" class="lazyload" data-srcset="https://cdn.jsdelivr.net/gh/volantis-x/cdn-org/logo/128/qzone.png" srcset="">
          
        </a>
      
    
      
        <a class="-mob-share-weibo" title="" rel="external nofollow noopener noreferrer noopener"
          
          target="_blank" href="http://service.weibo.com/share/share.php?url=https://www.yayako.cn/2020/06/08/HashMap/&title=HashMap源码解析 - Yayako's Blog&summary= "
          
          >
          
            <img src="https://cdn.jsdelivr.net/gh/volantis-x/cdn-org/logo/128/weibo.png" class="lazyload" data-srcset="https://cdn.jsdelivr.net/gh/volantis-x/cdn-org/logo/128/weibo.png" srcset="">
          
        </a>
      
    
      
    
      
    
  </div>
</div>



        
      
    </div>
  </div>


  
  

  
    <div class="prev-next">
      
        <a class='prev' href='/2020/06/08/LinkedHashMap/'>
          <p class='title'><i class="fas fa-chevron-left" aria-hidden="true"></i>LinkedHashMap</p>
          <p class='content'>继承自HashMap，在HashMap的基础上实现了双向链表来保证迭代顺序。
迭代顺序由双向链表结构保证，普通的存取还是通过原有的HashMap的逻辑。其顺序分为两种，插入顺序和访问顺序，在构造...</p>
        </a>
      
      
        <a class='next' href='/2020/06/07/Spring%20AOP%20%E6%BA%90%E7%A0%81%E8%A7%A3%E6%9E%90/'>
          <p class='title'>Spring AOP 源码解析<i class="fas fa-chevron-right" aria-hidden="true"></i></p>
          <p class='content'>jdk动态代理与cglib代理的区别在spring aop的实现中，

如果目标对象实现了接口，默认情况下会采用jdk动态代理实现aop，也可以强制使用cglib实现aop（添加库，配置prox...</p>
        </a>
      
    </div>
  
</article>


  

  <article class="post white-box reveal shadow" id="comments">
    <p ct><i class='fas fa-comments'></i> 评论</p>
    
    <div id="valine_container" class="valine_thread">
  <i class="fas fa-cog fa-spin fa-fw fa-2x"></i>
</div>

  </article>






</div>
<aside class='l_side'>
  
  
    
    



  <section class="widget toc-wrapper shadow desktop mobile" id="toc-div" >
    
  <header>
    
      <i class="fas fa-list fa-fw" aria-hidden="true"></i><span class='name'>本文目录</span>
    
  </header>


    <div class='content'>
        <ol class="toc"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84"><span class="toc-text">数据结构</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E4%B8%BA%E4%BB%80%E4%B9%88%E8%A6%81%E5%BC%95%E5%85%A5%E7%BA%A2%E9%BB%91%E6%A0%91%EF%BC%9F"><span class="toc-text">为什么要引入红黑树？</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E4%B8%BA%E4%BB%80%E4%B9%88%E6%98%AF8%EF%BC%9F"><span class="toc-text">为什么是8？</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E4%B8%BA%E4%BB%80%E4%B9%88%E6%98%AF6%EF%BC%9F"><span class="toc-text">为什么是6？</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%88%9D%E5%A7%8B%E5%8C%96"><span class="toc-text">初始化</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E4%B8%BA%E4%BB%80%E4%B9%88%E9%BB%98%E8%AE%A4%E5%88%9D%E5%A7%8B%E5%8C%96%E9%95%BF%E5%BA%A6%E4%B8%BA16%EF%BC%9F-%E4%B8%BA%E4%BB%80%E4%B9%88%E9%95%BF%E5%BA%A6%E4%B8%80%E5%AE%9A%E8%A6%81%E6%98%AF2%E7%9A%84%E5%B9%82%E6%AC%A1%EF%BC%9F"><span class="toc-text">为什么默认初始化长度为16？&#x2F;为什么长度一定要是2的幂次？</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#%E4%B8%8B%E6%A0%87%E8%AE%A1%E7%AE%97%E6%96%B9%E6%B3%95"><span class="toc-text">下标计算方法</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E6%80%8E%E4%B9%88%E8%AE%A1%E7%AE%97%E5%AE%B9%E9%87%8F%EF%BC%882%E7%9A%84%E5%B9%82%E6%AC%A1%E6%95%B0%EF%BC%89%EF%BC%9F"><span class="toc-text">怎么计算容量（2的幂次数）？</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E5%93%88%E5%B8%8C%E7%AE%97%E6%B3%95-%E5%8F%8A-%E6%89%B0%E5%8A%A8%E5%87%BD%E6%95%B0"><span class="toc-text">哈希算法 及 扰动函数</span></a></li></ol></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#put"><span class="toc-text">put</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#resize"><span class="toc-text">resize</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%89%A9%E5%AE%B9%E6%9D%A1%E4%BB%B6"><span class="toc-text">扩容条件</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%89%A9%E5%AE%B9%E6%96%B9%E5%BC%8F"><span class="toc-text">扩容方式</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E4%B8%BA%E4%BB%80%E4%B9%88HashMap%E6%98%AF%E7%BA%BF%E7%A8%8B%E4%B8%8D%E5%AE%89%E5%85%A8%E7%9A%84%EF%BC%9F"><span class="toc-text">为什么HashMap是线程不安全的？</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E4%B8%BA%E4%BB%80%E4%B9%88%E4%BC%9A%E9%81%87%E5%88%B0ConcurrentModificationException%E5%BC%82%E5%B8%B8"><span class="toc-text">为什么会遇到ConcurrentModificationException异常</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%88%86%E6%9E%90HashMap%E7%9A%84containsKey%E6%96%B9%E6%B3%95%E7%9A%84%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6"><span class="toc-text">分析HashMap的containsKey方法的时间复杂度</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%BA%90%E7%A0%81%E8%A7%A3%E8%AF%BB%EF%BC%88%E9%83%A8%E5%88%86%EF%BC%89"><span class="toc-text">源码解读（部分）</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#jdk1-7"><span class="toc-text">jdk1.7</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#%E6%9E%84%E9%80%A0%E5%87%BD%E6%95%B0"><span class="toc-text">构造函数</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#put-1"><span class="toc-text">put</span></a><ol class="toc-child"><li class="toc-item toc-level-5"><a class="toc-link" href="#addEntry"><span class="toc-text">addEntry</span></a></li></ol></li><li class="toc-item toc-level-4"><a class="toc-link" href="#get"><span class="toc-text">get</span></a><ol class="toc-child"><li class="toc-item toc-level-5"><a class="toc-link" href="#getEntry-containsKey"><span class="toc-text">getEntry &#x2F; containsKey</span></a></li></ol></li><li class="toc-item toc-level-4"><a class="toc-link" href="#resize-1"><span class="toc-text">resize</span></a><ol class="toc-child"><li class="toc-item toc-level-5"><a class="toc-link" href="#transfer"><span class="toc-text">transfer</span></a></li></ol></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#jdk1-8"><span class="toc-text">jdk1.8</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#%E5%A4%9A%E5%87%BA%E7%9A%84%E4%B8%A4%E4%B8%AA%E9%98%88%E5%80%BC"><span class="toc-text">多出的两个阈值</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E7%BB%93%E7%82%B9%E7%9A%84%E5%BC%95%E5%85%A5"><span class="toc-text">结点的引入</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E6%9E%84%E9%80%A0%E5%87%BD%E6%95%B0-1"><span class="toc-text">构造函数</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#put-2"><span class="toc-text">put</span></a><ol class="toc-child"><li class="toc-item toc-level-5"><a class="toc-link" href="#putVal"><span class="toc-text">putVal</span></a></li></ol></li><li class="toc-item toc-level-4"><a class="toc-link" href="#get-1"><span class="toc-text">get</span></a><ol class="toc-child"><li class="toc-item toc-level-5"><a class="toc-link" href="#getNode-containsKey"><span class="toc-text">getNode &#x2F; containsKey</span></a></li></ol></li><li class="toc-item toc-level-4"><a class="toc-link" href="#resize-2"><span class="toc-text">resize</span></a></li></ol></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#jdk1-7%E5%88%B01-8%E7%9A%84%E4%B8%BB%E8%A6%81%E5%8F%98%E5%8C%96"><span class="toc-text">jdk1.7到1.8的主要变化</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E6%94%B9%E5%8F%98"><span class="toc-text">数据结构改变</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E9%93%BE%E8%A1%A8%E8%8A%82%E7%82%B9%E6%8F%92%E5%85%A5"><span class="toc-text">链表节点插入</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%89%A9%E5%AE%B9"><span class="toc-text">扩容</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#%E6%89%A9%E5%AE%B9%E6%9D%A1%E4%BB%B6%E5%87%8F%E5%B0%91"><span class="toc-text">扩容条件减少</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E6%89%A9%E5%AE%B9%E6%96%B9%E5%BC%8F%EF%BC%88%E9%92%88%E5%AF%B9%E9%93%BE%E8%A1%A8%E8%80%8C%E8%A8%80%EF%BC%89"><span class="toc-text">扩容方式（针对链表而言）</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E6%89%A9%E5%AE%B9%E4%B8%8B%E6%A0%87%E8%AE%A1%E7%AE%97"><span class="toc-text">扩容下标计算</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E7%AE%80%E5%8C%96%E4%BA%86%E5%93%88%E5%B8%8C%E7%AE%97%E6%B3%95"><span class="toc-text">简化了哈希算法</span></a></li></ol></li></ol>
    </div>
  </section>


  


</aside>


   <!--此文件用来存放一些不方便取值的变量-->
<!--思路大概是将值藏到重加载的区域内-->

<script>
  window.pdata={}
  pdata.ispage=true;
  pdata.postTitle="HashMap源码解析";
  pdata.commentPath="";
  pdata.commentPlaceholder="";

  var l_header=document.getElementById("l_header");
  
  l_header.classList.remove("show");
  
</script>
 
        </div>
        
  
  <footer class="footer clearfix">
    <br><br>
    
      
        <div class="aplayer-container">
          


        </div>
      
    
      
        <br>
        <div class="social-wrapper">
          
            
          
            
          
            
          
        </div>
      
    
      
        <div><p>博客内容遵循 <a target="_blank" rel="noopener" href="https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh">署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议</a></p>
</div>
      
    
      
        
          <div><p><span id="lc-sv">本站总访问量为 <span id='number'><i class="fas fa-circle-notch fa-spin fa-fw" aria-hidden="true"></i></span> 次</span> <span id="lc-uv">访客数为 <span id='number'><i class="fas fa-circle-notch fa-spin fa-fw" aria-hidden="true"></i></span> 人</span></p>
</div>
        
      
    
      
        
      
    
      
        <div class='copyright'>
        <p><a href="/about/">Copyright © 2021 扭秧歌的一只泱</a> <strong>|</strong> <img src="https://yayako-blog.oss-cn-hangzhou.aliyuncs.com/settings/%E5%A4%87%E6%A1%88%E5%9B%BE%E6%A0%87.png" class="lazyload" data-srcset="https://yayako-blog.oss-cn-hangzhou.aliyuncs.com/settings/%E5%A4%87%E6%A1%88%E5%9B%BE%E6%A0%87.png" srcset="" alt="备案图标"> <a target="_blank" rel="noopener" href="http://www.beian.gov.cn/portal/registerSystemInfo?recordcode=33032402002017">浙公网安备33032402002017号</a> <strong>|</strong> <a target="_blank" rel="noopener" href="https://beian.miit.gov.cn/#/Integrated/index">浙ICP备20015559号</a></p>

        </div>
      
    
  </footer>


        <a
          id="s-top"
          class="fas fa-arrow-up fa-fw"
          href="javascript:void(0)"
        ></a>
      </div>
    </div>
    <div>
      <script>
window.volantis={};
window.volantis.loadcss=document.getElementById("loadcss");
/********************脚本懒加载函数********************************/
function loadScript(src, cb) {
var HEAD = document.getElementsByTagName('head')[0] || document.documentElement;
var script = document.createElement('script');
script.setAttribute('type','text/javascript');
if (cb) script.onload = cb;
script.setAttribute('src', src);
HEAD.appendChild(script);
}
//https://github.com/filamentgroup/loadCSS
var loadCSS = function( href, before, media, attributes ){
	var doc = window.document;
	var ss = doc.createElement( "link" );
	var ref;
	if( before ){
		ref = before;
	}
	else {
		var refs = ( doc.body || doc.getElementsByTagName( "head" )[ 0 ] ).childNodes;
		ref = refs[ refs.length - 1];
	}
	var sheets = doc.styleSheets;
	if( attributes ){
		for( var attributeName in attributes ){
			if( attributes.hasOwnProperty( attributeName ) ){
				ss.setAttribute( attributeName, attributes[attributeName] );
			}
		}
	}
	ss.rel = "stylesheet";
	ss.href = href;
	ss.media = "only x";
	function ready( cb ){
		if( doc.body ){
			return cb();
		}
		setTimeout(function(){
			ready( cb );
		});
	}
	ready( function(){
		ref.parentNode.insertBefore( ss, ( before ? ref : ref.nextSibling ) );
	});
	var onloadcssdefined = function( cb ){
		var resolvedHref = ss.href;
		var i = sheets.length;
		while( i-- ){
			if( sheets[ i ].href === resolvedHref ){
				return cb();
			}
		}
		setTimeout(function() {
			onloadcssdefined( cb );
		});
	};
	function loadCB(){
		if( ss.addEventListener ){
			ss.removeEventListener( "load", loadCB );
		}
		ss.media = media || "all";
	}
	if( ss.addEventListener ){
		ss.addEventListener( "load", loadCB);
	}
	ss.onloadcssdefined = onloadcssdefined;
	onloadcssdefined( loadCB );
	return ss;
};
</script>
<script>
  
  loadCSS("https://cdn.jsdelivr.net/npm/@fortawesome/fontawesome-free@5.14/css/all.min.css", window.volantis.loadcss);
  
  
  
  
</script>
<!-- required -->

<script src="https://cdn.jsdelivr.net/npm/jquery@3.5/dist/jquery.min.js"></script>

<script>
  function pjax_fancybox() {
    $(".md .gallery").find("img").each(function () { //渲染 fancybox
      var element = document.createElement("a"); // a 标签
      $(element).attr("class", "fancybox");
      $(element).attr("pjax-fancybox", "");  // 过滤 pjax
      $(element).attr("href", $(this).attr("src"));
      if ($(this).attr("data-original")) {
        $(element).attr("href", $(this).attr("data-original"));
      }
      $(element).attr("data-fancybox", "images");
      var caption = "";   // 描述信息
      if ($(this).attr('alt')) {  // 判断当前页面是否存在描述信息
        $(element).attr('data-caption', $(this).attr('alt'));
        caption = $(this).attr('alt');
      }
      var div = document.createElement("div");
      $(div).addClass("fancybox");
      $(this).wrap(div); // 最外层套 div ，其实主要作用还是 class 样式
      var span = document.createElement("span");
      $(span).addClass("image-caption");
      $(span).text(caption); // 加描述
      $(this).after(span);  // 再套一层描述
      $(this).wrap(element);  // 最后套 a 标签
    })
    $(".md .gallery").find("img").fancybox({
      selector: '[data-fancybox="images"]',
      hash: false,
      loop: false,
      closeClick: true,
      helpers: {
        overlay: {closeClick: true}
      },
      buttons: [
        "zoom",
        "close"
      ]
    });
  };
  function SCload_fancybox() {
    if ($(".md .gallery").find("img").length == 0) return;
    loadCSS("https://cdn.jsdelivr.net/npm/@fancyapps/fancybox@3.5.7/dist/jquery.fancybox.min.css", document.getElementById("loadcss"));
    setTimeout(function() {
      loadScript('https://cdn.jsdelivr.net/gh/fancyapps/fancybox@3.5.7/dist/jquery.fancybox.min.js', pjax_fancybox)
    }, 1);
  };
  $(function () {
    SCload_fancybox();
  });
</script>


<!-- internal -->

  
  
  
    
<script src="https://cdn.jsdelivr.net/npm/jquery-backstretch@2.1.18/jquery.backstretch.min.js"></script>

    <script type="text/javascript">
        var imgs=["https://yayako-blog.oss-cn-hangzhou.aliyuncs.com/cover/hd.jpg"];
        if ('false' == 'true') {
          function shuffle(arr){
            /*From countercurrent-time*/
            var n = arr.length;
            while(n--) {
              var index = Math.floor(Math.random() * n);
              var temp = arr[index];
              arr[index] = arr[n];
              arr[n] = temp;
            }
          }
          shuffle(imgs);
        }
	  function Pjax_backstretch(){
        
          $.backstretch(
            imgs,
          {
            duration: "10000",
            fade: "1500"
          });
        
	  }
	  loadScript("https://cdn.jsdelivr.net/npm/jquery-backstretch@2.1.18/jquery.backstretch.min.js",Pjax_backstretch)
    </script>
  




<script>
  function loadIssuesJS() {
    if ($(".md").find(".issues-api").length == 0) return;
    setTimeout(function() {
	
	  loadScript('/js/issues.js');
	
    }, 1);
  };
  $(function () {
    loadIssuesJS();
  });
</script>



  <script defer src="https://cdn.jsdelivr.net/npm/vanilla-lazyload@17.1.0/dist/lazyload.min.js"></script>
<script>
  // https://www.npmjs.com/package/vanilla-lazyload
  // Set the options globally
  // to make LazyLoad self-initialize
  window.lazyLoadOptions = {
    elements_selector: ".lazyload",
    threshold: 0
  };
  // Listen to the initialization event
  // and get the instance of LazyLoad
  window.addEventListener(
    "LazyLoad::Initialized",
    function (event) {
      window.lazyLoadInstance = event.detail.instance;
    },
    false
  );
  document.addEventListener('DOMContentLoaded', function () {
    lazyLoadInstance.update();
  });
  document.addEventListener('pjax:complete', function () {
    lazyLoadInstance.update();
  });
</script>




  
  
    <script>
      window.FPConfig = {
        delay: 0,
        ignoreKeywords: [],
        maxRPS: 5,
        hoverDelay: 25
      };
    </script>
    <script defer src="https://cdn.jsdelivr.net/gh/gijo-varghese/flying-pages@2.1.2/flying-pages.min.js"></script>
  




  <script src="https://cdn.jsdelivr.net/npm/clipboard@2/dist/clipboard.min.js"></script>
<script>
    var clipboard = new ClipboardJS('.btn-copy', {
        target: function (trigger) {
            return trigger.nextElementSibling
        }
    });
    function wait(callback, seconds) {
        var timelag = null;
        timelag = window.setTimeout(callback, seconds)
    }
    function pjax_initCopyCode() {
		if($(".highlight .code pre").length+$(".article pre code").length==0)return;
        var copyHtml = '';
        copyHtml += '<button class="btn-copy" data-clipboard-snippet="">';
        copyHtml += '<i class="fas fa-copy"></i><span>COPY</span>';
        copyHtml += '</button>';
        $(".highlight .code pre").before(copyHtml);
        $(".article pre code").before(copyHtml);
        clipboard.off('success').on('success', function (e) {
            let $btn = $(e.trigger);
            $btn.addClass('copied');
            let $icon = $($btn.find('i'));
            $icon.removeClass('fa-copy');
            $icon.addClass('fa-check-circle');
            let $span = $($btn.find('span'));
            $span[0].innerText = 'COPIED';
            wait(function () {
                $icon.removeClass('fa-check-circle');
                $icon.addClass('fa-copy');
                $span[0].innerText = 'COPY'
            }, 2000)
        });
        clipboard.off('error').on('error', function (e) {
            e.clearSelection();
            let $btn = $(e.trigger);
            $btn.addClass('copy-failed');
            let $icon = $($btn.find('i'));
            $icon.removeClass('fa-copy');
            $icon.addClass('fa-times-circle');
            let $span = $($btn.find('span'));
            $span[0].innerText = 'COPY FAILED';
            wait(function () {
                $icon.removeClass('fa-times-circle');
                $icon.addClass('fa-copy');
                $span[0].innerText = 'COPY'
            }, 2000)
        })
    }
    $(function () {
        pjax_initCopyCode()
    });
</script>




   <script src="https://cdn.jsdelivr.net/npm/scrollreveal@4.0.6/dist/scrollreveal.min.js"></script>
<script type="text/javascript">
  function pjax_scrollrebeal() {
    ScrollReveal().reveal('.l_main .reveal', {
      distance: '32px',
      duration: '800',
      interval: '20',
      scale: '1',
      easing: 'ease-out'
    });
  }
  $(function () {
    pjax_scrollrebeal();
  });
</script>






  
  
<script src="https://cdn.jsdelivr.net/npm/valine@1.4/dist/Valine.min.js"></script>


<script>
  function emoji(path, idx, ext) {
    return path + "/" + path + "-" + idx + "." + ext;
  }
  var emojiMaps = {};
  for (var i = 1; i <= 54; i++) {
    emojiMaps['tieba-' + i] = emoji('tieba', i, 'png');
  }
  for (var i = 1; i <= 101; i++) {
    emojiMaps['qq-' + i] = emoji('qq', i, 'gif');
  }
  for (var i = 1; i <= 116; i++) {
    emojiMaps['aru-' + i] = emoji('aru', i, 'gif');
  }
  for (var i = 1; i <= 125; i++) {
    emojiMaps['twemoji-' + i] = emoji('twemoji', i, 'png');
  }
  for (var i = 1; i <= 4; i++) {
    emojiMaps['weibo-' + i] = emoji('weibo', i, 'png');
  }
  function pjax_valine() {
    if(!document.querySelectorAll("#valine_container")[0])return;
    let pagePlaceholder = pdata.commentPlaceholder || "快来评论吧~";
    let path = pdata.commentPath;
    if (path.length == 0) {
      let defaultPath = '';
      path = defaultPath || decodeURI(window.location.pathname);
    }
    var valine = new Valine();
    valine.init(Object.assign({"js":"https://cdn.jsdelivr.net/npm/valine@1.4/dist/Valine.min.js","path":null,"placeholder":"快来评论吧~","appId":"crkoKrezsl4I7UWQjAvOy2N1-gzGzoHsz","appKey":"OUvAeTn1CnCmGFdNYVH00G0S","meta":["nick","mail","link"],"requiredFields":["nick","mail"],"enableQQ":true,"recordIP":false,"avatar":"robohash","pageSize":10,"lang":"zh-cn","highlight":true,"visitor":true,"mathJax":false}, {
      el: '#valine_container',
      path: path,
      placeholder: pagePlaceholder,
      emojiCDN: 'https://cdn.jsdelivr.net/gh/volantis-x/cdn-emoji/valine/',
      emojiMaps: emojiMaps,
    }))
  }
  $(function () {
    pjax_valine();
  });
</script>





  
<script src="/js/app.js"></script>



<!-- optional -->

  <script>
const SearchServiceimagePath="https://cdn.jsdelivr.net/gh/volantis-x/cdn-volantis@master/img/";
const ROOT =  ("/" || "/").endsWith('/') ? ("/" || "/") : ("//" || "/" );

$('.input.u-search-input').one('focus',function(){
	
		loadScript('/js/search/hexo.js',setSearchService);
	
})

function listenSearch(){
  
    customSearch = new HexoSearch({
      imagePath: SearchServiceimagePath
    });
  
}
function setSearchService() {
	listenSearch();
	
		document.addEventListener("pjax:success", listenSearch);
	
}
</script>











  <script defer>

  const LCCounter = {
    app_id: 'u9j57bwJod4EDmXWdxrwuqQT-MdYXbMMI',
    app_key: 'jfHtEKVE24j0IVCGHbvuFClp',
    custom_api_server: '',

    // 查询存储的记录
    getRecord(Counter, url, title) {
      return new Promise(function (resolve, reject) {
        Counter('get', '/classes/Counter?where=' + encodeURIComponent(JSON.stringify({url})))
          .then(resp => resp.json())
          .then(({results, code, error}) => {
            if (code === 401) {
              throw error;
            }
            if (results && results.length > 0) {
              var record = results[0];
              resolve(record);
            } else {
              Counter('post', '/classes/Counter', {url, title: title, times: 0})
                .then(resp => resp.json())
                .then((record, error) => {
                  if (error) {
                    throw error;
                  }
                  resolve(record);
                }).catch(error => {
                console.error('Failed to create', error);
                reject(error);
              });
            }
          }).catch((error) => {
          console.error('LeanCloud Counter Error:', error);
          reject(error);
        });
      })
    },

    // 发起自增请求
    increment(Counter, incrArr) {
      return new Promise(function (resolve, reject) {
        Counter('post', '/batch', {
          "requests": incrArr
        }).then((res) => {
          res = res.json();
          if (res.error) {
            throw res.error;
          }
          resolve(res);
        }).catch((error) => {
          console.error('Failed to save visitor count', error);
          reject(error);
        });
      });
    },

    // 构建自增请求体
    buildIncrement(objectId) {
      return {
        "method": "PUT",
        "path": `/1.1/classes/Counter/${ objectId }`,
        "body": {
          "times": {
            '__op': 'Increment',
            'amount': 1
          }
        }
      }
    },

    // 校验是否为有效的 UV
    validUV() {
      var key = 'LeanCloudUVTimestamp';
      var flag = localStorage.getItem(key);
      if (flag) {
        // 距离标记小于 24 小时则不计为 UV
        if (new Date().getTime() - parseInt(flag) <= 86400000) {
          return false;
        }
      }
      localStorage.setItem(key, new Date().getTime().toString());
      return true;
    },

    addCount(Counter) {
      var enableIncr = '' === 'true' && window.location.hostname !== 'localhost';
      enableIncr = true;
      var getterArr = [];
      var incrArr = [];
      // 请求 PV 并自增
      var pvCtn = document.querySelector('#lc-sv');
      if (pvCtn || enableIncr) {
        var pvGetter = this.getRecord(Counter, 'https://www.yayako.cn' + '/#lc-sv', 'Visits').then((record) => {
          incrArr.push(this.buildIncrement(record.objectId))
          var eles = document.querySelectorAll('#lc-sv #number');
          if (eles.length > 0) {
            eles.forEach((el,index,array)=>{
              el.innerText = record.times + 1;
              if (pvCtn) {
                pvCtn.style.display = 'inline';
              }
            })
          }
        });
        getterArr.push(pvGetter);
      }

      // 请求 UV 并自增
      var uvCtn = document.querySelector('#lc-uv');
      if (uvCtn || enableIncr) {
        var uvGetter = this.getRecord(Counter, 'https://www.yayako.cn' + '/#lc-uv', 'Visitors').then((record) => {
          var vuv = this.validUV();
          vuv && incrArr.push(this.buildIncrement(record.objectId))
          var eles = document.querySelectorAll('#lc-uv #number');
          if (eles.length > 0) {
            eles.forEach((el,index,array)=>{
              el.innerText = record.times + (vuv ? 1 : 0);
              if (uvCtn) {
                uvCtn.style.display = 'inline';
              }
            })
          }
        });
        getterArr.push(uvGetter);
      }

      // 请求文章的浏览数，如果是当前页面就自增
      var allPV = document.querySelectorAll('#lc-pv');
      if (allPV.length > 0 || enableIncr) {
        for (i = 0; i < allPV.length; i++) {
          let pv = allPV[i];
          let title = pv.getAttribute('data-title');
          var url = 'https://www.yayako.cn' + pv.getAttribute('data-path');
          if (url) {
            var viewGetter = this.getRecord(Counter, url, title).then((record) => {
              // 是当前页面就自增
              let curPath = window.location.pathname;
              if (curPath.includes('index.html')) {
                curPath = curPath.substring(0, curPath.lastIndexOf('index.html'));
              }
              if (pv.getAttribute('data-path') == curPath) {
                incrArr.push(this.buildIncrement(record.objectId));
              }
              if (pv) {
                var ele = pv.querySelector('#lc-pv #number');
                if (ele) {
                  if (pv.getAttribute('data-path') == curPath) {
                    ele.innerText = (record.times || 0) + 1;
                  } else {
                    ele.innerText = record.times || 0;
                  }
                  pv.style.display = 'inline';
                }
              }
            });
            getterArr.push(viewGetter);
          }
        }
      }

      // 如果启动计数自增，批量发起自增请求
      if (enableIncr) {
        Promise.all(getterArr).then(() => {
          incrArr.length > 0 && this.increment(Counter, incrArr);
        })
      }

    },


    fetchData(api_server) {
      var Counter = (method, url, data) => {
        return fetch(`${ api_server }/1.1${ url }`, {
          method,
          headers: {
            'X-LC-Id': this.app_id,
            'X-LC-Key': this.app_key,
            'Content-Type': 'application/json',
          },
          body: JSON.stringify(data)
        });
      };
      this.addCount(Counter);
    },

    refreshCounter() {
      var api_server = this.app_id.slice(-9) !== '-MdYXbMMI' ? this.custom_api_server : `https://${ this.app_id.slice(0, 8).toLowerCase() }.api.lncldglobal.com`;
      if (api_server) {
        this.fetchData(api_server);
      } else {
        fetch('https://app-router.leancloud.cn/2/route?appId=' + this.app_id)
          .then(resp => resp.json())
          .then(({api_server}) => {
            this.fetchData('https://' + api_server);
          });
      }
    }

  };

  LCCounter.refreshCounter();

  document.addEventListener('pjax:complete', function () {
    LCCounter.refreshCounter();
  });
</script>








<script>
function listennSidebarTOC() {
  const navItems = document.querySelectorAll(".toc li");
  if (!navItems.length) return;
  const sections = [...navItems].map((element) => {
    const link = element.querySelector(".toc-link");
    const target = document.getElementById(
      decodeURI(link.getAttribute("href")).replace("#", "")
    );
    link.addEventListener("click", (event) => {
      event.preventDefault();
      window.scrollTo({
		top: target.offsetTop + 100,
		
		behavior: "smooth"
		
	  });
    });
    return target;
  });

  function activateNavByIndex(target) {
    if (target.classList.contains("active-current")) return;

    document.querySelectorAll(".toc .active").forEach((element) => {
      element.classList.remove("active", "active-current");
    });
    target.classList.add("active", "active-current");
    let parent = target.parentNode;
    while (!parent.matches(".toc")) {
      if (parent.matches("li")) parent.classList.add("active");
      parent = parent.parentNode;
    }
  }

  function findIndex(entries) {
    let index = 0;
    let entry = entries[index];
    if (entry.boundingClientRect.top > 0) {
      index = sections.indexOf(entry.target);
      return index === 0 ? 0 : index - 1;
    }
    for (; index < entries.length; index++) {
      if (entries[index].boundingClientRect.top <= 0) {
        entry = entries[index];
      } else {
        return sections.indexOf(entry.target);
      }
    }
    return sections.indexOf(entry.target);
  }

  function createIntersectionObserver(marginTop) {
    marginTop = Math.floor(marginTop + 10000);
    let intersectionObserver = new IntersectionObserver(
      (entries, observe) => {
        let scrollHeight = document.documentElement.scrollHeight + 100;
        if (scrollHeight > marginTop) {
          observe.disconnect();
          createIntersectionObserver(scrollHeight);
          return;
        }
        let index = findIndex(entries);
        activateNavByIndex(navItems[index]);
      },
      {
        rootMargin: marginTop + "px 0px -100% 0px",
        threshold: 0,
      }
    );
    sections.forEach((element) => {
      element && intersectionObserver.observe(element);
    });
  }
  createIntersectionObserver(document.documentElement.scrollHeight);
}

document.addEventListener("DOMContentLoaded", listennSidebarTOC);
document.addEventListener("pjax:success", listennSidebarTOC);
</script>

<!-- more -->

  


<script src="https://cdn.jsdelivr.net/npm/pjax@0.2.8/pjax.min.js"></script>


<script>
    var pjax;
    document.addEventListener('DOMContentLoaded', function () {
      pjax = new Pjax({
        elements: 'a[href]:not([href^="#"]):not([href="javascript:void(0)"]):not([pjax-fancybox])',
        selectors: [
          "title",
          "#l_cover",
          "#pjax-container",
          "#pjax-header-nav-list"
        ],
        cacheBust: false,   // url 地址追加时间戳，用以避免浏览器缓存
        timeout: 5000
      });
    });

    document.addEventListener('pjax:send', function (e) {
      //window.stop(); // 相当于点击了浏览器的停止按钮

      try {
        var currentUrl = window.location.pathname;
        var targetUrl = e.triggerElement.href;
        var banUrl = [""];
        if (banUrl[0] != "") {
          banUrl.forEach(item => {
            if(currentUrl.indexOf(item) != -1 || targetUrl.indexOf(item) != -1) {
              window.location.href = targetUrl;
            }
          });
        }
      } catch (error) {}

      window.subData = null; // 移除标题（用于一二级导航栏切换处）
      if (typeof $.fancybox != "undefined") {
        $.fancybox.close();    // 关闭弹窗
      }
      volantis.$switcher.removeClass('active'); // 关闭移动端激活的搜索框
      volantis.$header.removeClass('z_search-open'); // 关闭移动端激活的搜索框
      volantis.$wrapper.removeClass('sub'); // 跳转页面时关闭二级导航

      // 解绑事件 避免重复监听
      volantis.$topBtn.unbind('click');
      $('.menu a').unbind('click');
      $(window).unbind('resize');
      $(window).unbind('scroll');
      $(document).unbind('scroll');
      $(document).unbind('click');
      $('body').unbind('click');
	  
    });

    document.addEventListener('pjax:complete', function () {
      // 关于百度统计对 SPA 页面的处理：
      // 方案一：百度统计>管理>单页应用设置中，打开开启按钮即可对SPA进行统计。 https://tongji.baidu.com/web/help/article?id=324
      // 方案二：取消注释下列代码。 https://tongji.baidu.com/web/help/article?id=235
       

      // 关于谷歌统计对 SPA 页面的处理：
      // 当应用以动态方式加载内容并更新地址栏中的网址时，也应该更新通过 gtag.js 存储的网页网址。
      // https://developers.google.cn/analytics/devguides/collection/gtagjs/single-page-applications?hl=zh-cn
      


      $('.nav-main').find('.list-v').not('.menu-phone').removeAttr("style",""); // 移除小尾巴的移除
      $('.menu-phone.list-v').removeAttr("style",""); // 移除小尾巴的移除
      $('script[data-pjax], .pjax-reload script').each(function () {
        $(this).parent().append($(this).remove());
      });
      try{
          if (typeof $.fancybox == "undefined") {
            SCload_fancybox();
          } else {
            pjax_fancybox();
          }
        
		  Pjax_backstretch()
        
        
        
          pjax_scrollrebeal();
        
        if (typeof IssuesAPI == "undefined") {
          loadIssuesJS();
        }
        
          pjax_initCopyCode();
        
        
          pjax_valine();
        
        
        
        
        
        
      } catch (e) {
        console.log(e);
      }
	  
    });

    document.addEventListener('pjax:error', function (e) {
	  
      window.location.href = e.triggerElement.href;
    });
</script>
 
    </div>
  </body>
</html>
